peteroupc.github.io/jump.html at master · peteroupc/peteroupc.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<!DOCTYPE html><html  xmlns:dc="http://purl.org/dc/terms/" xmlns:og="http://ogp.me/ns#" ><head><meta http-equiv=Content-Type content="text/html; charset=utf-8"><title>Notes on Jumping PRNGs Ahead</title><meta name="citation_pdf_url" content="https://peteroupc.github.io/jump.pdf"><meta name="citation_url" content="https://peteroupc.github.io/jump.html"><meta name="citation_title" content="Notes on Jumping PRNGs Ahead"><meta name="dc.date" content="2025-09-30"><meta name="citation_date" content="2025/09/30"><meta name="citation_publication_date" content="2025/09/30"><meta name="citation_online_date" content="2025/09/30"><meta name="og:title" content="Notes on Jumping PRNGs Ahead"><meta name="og:type" content="article"><meta name="og:url" content="https://peteroupc.github.io/jump.html"><meta name="og:site_name" content="peteroupc.github.io"><meta name="dc.format" content="text/html"><meta name="dc.language" content="en"><meta name="title" content="Notes on Jumping PRNGs Ahead"><meta name="dc.title" content="Notes on Jumping PRNGs Ahead"><meta name="twitter:title" content="Notes on Jumping PRNGs Ahead"><meta name="dc.creator" content="Peter Occil"/><meta name="author" content="Peter Occil"/><meta name="citation_author" content="Peter Occil"/><meta name="viewport" content="width=device-width"><link rel=stylesheet type="text/css" href="/style.css">
            <script type="text/x-mathjax-config"> MathJax.Hub.Config({"HTML-CSS": { availableFonts: ["STIX","TeX"], linebreaks: { automatic:true }, preferredFont: "TeX" },
                    tex2jax: { displayMath: [ ["$$","$$"], ["\\[", "\\]"] ], inlineMath: [ ["$", "$"], ["\\\\(","\\\\)"] ], processEscapes: true } });
            </script><script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS_HTML-full"></script></head><body>  <div class="header">
<nav><p><a href="#navigation">Menu</a> - <a href="#top">Top</a> - <a href="/">Home</a></nav></div>
<div class="mainarea" id="top">
<p><a id="Notes_on_Jumping_PRNGs_Ahead"></a></p>

<h2 id="notes-on-jumping-prngs-ahead">Notes on Jumping PRNGs Ahead</h2>

<p><a href="mailto:poccil14@gmail.com"><strong>Peter Occil</strong></a></p>

<p>Some pseudorandom number generators (PRNGs) have an efficient way to advance their state as though a huge number of PRNG outputs were discarded.  Notes on how they work are described in the following sections.</p>

<p><a id="F2_linear_PRNGs"></a></p>

<h3 id="fsub2sub-linear-prngs">F<sub>2</sub>-linear PRNGs</h3>

<p>For some PRNGs, each bit of the PRNG’s state can be described as a linear recurrence on its entire state.  These PRNGs are called <em>F<sub>2</sub>-linear PRNGs</em>, and they include the following:</p>

<ul>
  <li>Linear congruential generators (LCGs) with a power-of-two modulus.</li>
  <li>Xorshift PRNGs.</li>
  <li>PRNGs in the xoroshiro and xoshiro families.</li>
  <li>Linear or generalized feedback shift register generators, including Mersenne Twister.</li>
</ul>

<p>For an F<sub>2</sub>-linear PRNG, there is an efficient way to discard a given (and arbitrary) number of its outputs (to “jump the PRNG ahead”).  This jump-ahead strategy is further described in (Haramoto et al., 2008)<sup id="fnref:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>.  See also (Vigna 2017)<sup id="fnref:2"><a href="#fn:2" class="footnote" rel="footnote" role="doc-noteref">2</a></sup>. To calculate the jump-ahead parameters needed to advance the PRNG N steps:</p>

<ol>
  <li>Build <code>M</code>, an S×S matrix of zeros and ones that describes the linear transformation of the PRNG’s state, where S is the size of that state in bits.  For an example, see sections 3.1 and 3.2 of (Blackman and Vigna 2019)<sup id="fnref:3"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">3</a></sup>, where it should be noted that the additions inside the matrix are actually XORs.</li>
  <li>
    <p>Find the <em>characteristic polynomial</em> of <code>M</code>.  This has to be done in the two-element field F<sub>2</sub>, so that each coefficient of the polynomial is either 0 or 1.</p>

    <p>For example, SymPy’s <code>charpoly()</code> method alone is inadequate for this purpose, since it doesn’t operate on the correct field.  However, it’s easy to adapt that method’s output for the field F<sub>2</sub>: even coefficients become zeros and odd coefficients become ones.</p>

    <p>Note that for a linear feedback shift register (LFSR) generator, the characteristic polynomial’s coefficients are 1 for each of its “taps” (and “tap” 0), and 0 elsewhere.  For example, an LFSR generator with taps 6 and 8 has the characteristic polynomial x<sup>8</sup> + x<sup>6</sup> + 1.</p>

    <p>The section “Jump Parameters for Some PRNGs” shows characteristic polynomials for some PRNGs and one way their coefficients can be represented.</p>
  </li>
  <li>Calculate <code>powmodf2(2, N, CP)</code>, where <code>powmodf2</code> is a modular power function that calculates <code>2^N mod CP</code> in the field F<sub>2</sub>, and <code>CP</code> is the characteristic polynomial. (<code>N</code> is the number of PRNG outputs to discard.)  Ordinary modular power functions, such as BigInteger’s <code>modPow</code> method, won’t work here, even if the polynomial is represented in the manner described in “Jump Parameters for Some PRNGs”.</li>
  <li>
    <p>The result is a <em>jump polynomial</em> for jumping the PRNG ahead N steps, that is, for discarding N outputs of the PRNG.</p>

    <p>An example of its use is found in the <code>jump</code> and <code>long_jump</code> functions in the <a href="http://xoshiro.di.unimi.it/xoroshiro128plus.c"><strong><code>xoroshiro128plus</code> source code</strong></a>, which are identical except for the jump polynomial.  In both functions, the jump polynomial’s coefficients are packed into a 128-bit integer (as described in “Jump Parameters for Some PRNGs”), which is then split into the lower 64 bits and the upper 64 bits, in that order.</p>
  </li>
</ol>

<p><a id="Counter_Based_PRNGs"></a></p>

<h3 id="counter-based-prngs">Counter-Based PRNGs</h3>

<p>Counter-based PRNGs, in which their state is updated simply by incrementing a counter, can be trivially jumped ahead just by changing the seed, the counter, or both (Salmon et al. 2011)<sup id="fnref:4"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>.</p>

<p><a id="Multiple_Recursive_Generators"></a></p>

<h3 id="multiple-recursive-generators">Multiple Recursive Generators</h3>

<p>A <em>multiple recursive generator</em> (MRG) generates numbers by transforming its state using the following formula: <code>x(k) = (x(k-1)*A(1) + x(k-2)*A(2) + ... + x(k-n)*A(n)) mod modulus</code>, where <code>A(i)</code> are the <em>multipliers</em> and <code>modulus</code> is the <em>modulus</em>.</p>

<p>For an MRG, the following matrix (<code>M</code>) describes the state transition <code>[x(k-n), ..., x(k-1)]</code> to <code>[x(k-n+1), ..., x(k)]</code> (mod <code>modulus</code>):</p>

<pre> | 0   1   0  ...  0  |
 | 0   0   1  ...  0  |
 | .   .   .  ... ... |
 | 0   0   0  ...  1  |
 |A(n)A(n A(n ... A(1)|
 |     -1) -2)        |
</pre>

<p>To calculate the parameter needed to jump the MRG ahead N steps, calculate <code>M</code><sup>N</sup> mod <code>modulus</code>; the result is a <em>jump matrix</em> <code>J</code>.</p>

<p>Then, to jump the MRG ahead N steps, calculate <code>J * S</code> mod <code>modulus</code>, where <code>J</code> is the jump matrix and <code>S</code> is the state in the form of a column vector; the result is a new state for the MRG.</p>

<p>This technique was mentioned (but for binary matrices) in Haramoto, in sections 1 and 3.1.  They point out, though, that it isn’t efficient if the transition matrix is large.  See also (L’Ecuyer et al., 2002)<sup id="fnref:5"><a href="#fn:5" class="footnote" rel="footnote" role="doc-noteref">5</a></sup>.</p>

<p><a id="Example"></a></p>

<h4 id="example">Example</h4>

<p>A multiple recursive generator with a modulus of 1449 has the following transition matrix:</p>

<pre>|  0   1   0  |
|  0   0   1  |
| 444 342 499 |
</pre>

<p>To calculate the 3 × 3 jump matrix to jump 100 steps from this MRG, raise this matrix to the power of 100 then take the result’s elements mod 1449.  One way to do this is the “square-and-multiply” method, described by D. Knuth in <em>The Art of Computer Programming</em>: Set J to the identity matrix, N to 100, and M to a copy of the transition matrix, then while N is greater than 0:</p>

<ol>
  <li>If N is odd<sup id="fnref:6"><a href="#fn:6" class="footnote" rel="footnote" role="doc-noteref">6</a></sup>, multiply J by M then take J’s elements mod 1449.</li>
  <li>Divide N by 2 and round down, then multiply M by M then take M’s elements mod 1449.</li>
</ol>

<p>The resulting J is a <em>jump matrix</em> as follows:</p>

<pre>| 156   93  1240 |
| 1389 1128  130 |
| 1209  930  793 |
</pre>

<p>Transforming the MRG’s state with J (and taking its elements mod 1449) will transform the state as though 100 outputs were discarded from the MRG.</p>

<p><a id="Linear_Congruential_Generators"></a></p>

<h3 id="linear-congruential-generators">Linear Congruential Generators</h3>

<p>A <em>linear congruential generator</em> (LCG) generates numbers by transforming its state using the following formula: <code>x(k) = (x(k-1)*a + c) mod modulus</code>, where <code>a</code> is the <em>multiplier</em>, <code>c</code> is the additive constant, and <code>modulus</code> is the <em>modulus</em>.</p>

<p>An efficient way to jump an LCG ahead is described in (Brown 1994)<sup id="fnref:7"><a href="#fn:7" class="footnote" rel="footnote" role="doc-noteref">7</a></sup>. This also applies to LCGs that transform each <code>x(k)</code> before giving out it, such as M.O’Neill’s PCG32 and PCG64.</p>

<p>An MRG with only one multiplier expresses the special case of an LCG with <code>c = 0</code> (also known as a <em>multiplicative</em> LCG).  For <code>c</code> other than 0, the following matrix describes the state transition <code>[x(k-1), 1]</code> to <code>[x(k), 1]</code> (mod <code>modulus</code>):</p>

<pre> | a   c |
 | 0   1 |
</pre>

<p>Jumping the LCG ahead can then be done using this matrix as described in the previous section.</p>

<p><a id="Multiply_with_Carry_Add_with_Carry_Subtract_with_Borrow"></a></p>

<h3 id="multiply-with-carry-add-with-carry-subtract-with-borrow">Multiply-with-Carry, Add-with-Carry, Subtract-with-Borrow</h3>

<p>There are implementations for jumping a multiply-with-carry (MWC) PRNG ahead, but <a href="https://github.com/rsaucier/Random/blob/3a7981bd6a8ac6d4507e9630393303b18e8967ca/kiss.h"><strong>only in source-code form</strong></a>.  I am not aware of an article or paper that describes how jumping an MWC PRNG ahead works.</p>

<p>I am not aware of any efficient ways to jump an add-with-carry or subtract-with-borrow PRNG ahead an arbitrary number of steps.</p>

<p><a id="Combined_PRNGs"></a></p>

<h3 id="combined-prngs">Combined PRNGs</h3>

<p>A combined PRNG can be jumped ahead N steps by jumping each of its components ahead N steps.</p>

<p><a id="Jump_Parameters_for_Some_PRNGs"></a></p>

<h3 id="jump-parameters-for-some-prngs">Jump Parameters for Some PRNGs</h3>

<p>The following table shows the characteristic polynomial and jump polynomials for some PRNG families.  In the table:</p>

<ul>
  <li>Each number before the colon in the jump polynomial column is the number of PRNG outputs discarded when the corresponding jump polynomial is used.</li>
  <li>Each polynomial’s coefficients are zeros and ones, so the table shows them as a base-16 integer that stores the coefficients as individual bits: the least significant bit is the degree-0 coefficient, the next bit is the degree-1 coefficient, and so on.  For example, the integer 0x23 stores the coefficients of the polynomial x<sup>5</sup> + x + 1.</li>
  <li>Each characteristic polynomial’s highest coefficient is x<sup>n</sup>, where n is the PRNG’s state size.  Thus, the table shows it as a base-16 integer with n plus one bits.</li>
  <li>“‘Period’/φ” means the PRNG’s maximum cycle length divided by the golden ratio, and rounded to the closest odd integer; this jump parameter is chosen to avoid overlapping number sequences as much as possible (see also <a href="https://docs.scipy.org/doc/numpy/reference/random/parallel.html"><strong>NumPy documentation</strong></a>).</li>
</ul>

<p> </p>

<table>
  <thead>
    <tr>
      <th>PRNG</th>
      <th>Characteristic Polynomial</th>
      <th>Jump Polynomials</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>xoroshiro64</td>
      <td>0x1053be9da6e2286c1</td>
      <td>2<sup>32</sup>: 0x4cbf99bd77fcd1a0<br />2<sup>48</sup>: 0xb4e7e4633f1f8b95<br />“Period”/φ: 0x751f355609af0e3b</td>
    </tr>
    <tr>
      <td>xoshiro128</td>
      <td>0x100fc65a2006254b11b489db6de18fc01</td>
      <td>2<sup>32</sup>: 0xf8aed94730b948df3be07b8f7afe108<br />2<sup>48</sup>: 0xdeaa4ca2dec5bb9a87a4583dcb56667c<br />2<sup>64</sup>: 0x77f2db5b6fa035c3f542d2d38764000b<br />2<sup>96</sup>: 0x1c580662ccf5a0ef0b6f099fb523952e<br />“Period”/φ: 0x338b58d0590169928fda8fd5d1cf96b6</td>
    </tr>
    <tr>
      <td>xoroshiro128 (except ++)</td>
      <td>0x10008828e513b43d5095b8f76579aa001</td>
      <td>2<sup>32</sup>: 0xd4e95eef9edbdbc6fad843622b252c78<br />2<sup>48</sup>: 0x9b19ba6b3752065ad769cfc9028deb78<br />2<sup>64</sup>: 0x170865df4b3201fcdf900294d8f554a5<br />2<sup>96</sup>: 0xdddf9b1090aa7ac1d2a98b26625eee7b<br />“Period”/φ: 0xc1c620fd7bf598c34a2828365a7df3e0</td>
    </tr>
    <tr>
      <td>xoroshiro128++</td>
      <td>0x10031bcf2f855d6e58dae70779760b081</td>
      <td>2<sup>32</sup>: 0x2e1bcf52f1051044fcceec21d5c306d9<br />2<sup>48</sup>: 0xc8462a08ab3d7f9b99030a888c867939<br />2<sup>64</sup>: 0x992ccaf6a6fca052bd7a6a6e99c2ddc<br />2<sup>96</sup>: 0x9c6e6877736c46e3360fd5f2cf8d5d99<br />“Period”/φ: 0x1b4c7a8989405b16d3e4e127a6a11513</td>
    </tr>
    <tr>
      <td>xoshiro256</td>
      <td>0x10003c03c3f3ecb1904b4edcf26259f850280002bcefd1a5e9d116f2bb0f0f001</td>
      <td>2<sup>32</sup>: 0xe055d3520fdb9d7214fafc0fbdbc2087d8d0632bd08e6ac58120d583c112f69<br />2<sup>48</sup>: 0x5f728be2c97e9066474579292f705634f825539dee5e4763f11fb4faea62c7f1<br />2<sup>64</sup>: 0x12e4a2fbfc19bff934faff184785c20ab60d6c5b8c78f106b13c16e8096f0754<br />2<sup>96</sup>: 0x31eebb6c82a9615fb27c05962ea56a13cdb45d7def42c317148c356c3114b7a9<br />2<sup>128</sup>: 0x39abdc4529b1661ca9582618e03fc9aad5a61266f0c9392c180ec6d33cfd0aba<br />2<sup>160</sup>: 0xf567382197055bf04823b45b89dc689c69e6e6e431a2d40bc04b4f9c5d26c200<br />2<sup>192</sup>: 0x39109bb02acbe63577710069854ee241c5004e441c522fb376e15d3efefdcbbf<br />2<sup>224</sup>: 0xa2b5d83a373c7ac2f31d2e03157bc387d317530723ab526a0c7840cbc3b121ad<br />“Period”/φ: 0x294e2bac089b06c7d4ce5d1a031b6cf8787f49127b37f506ac1c9e5f5f53046c</td>
    </tr>
  </tbody>
</table>

<p><a id="Acknowledgments"></a></p>

<h3 id="acknowledgments">Acknowledgments</h3>

<p>Sebastiano Vigna reviewed this page and gave comments.</p>

<p><a id="Notes"></a></p>

<h2 id="notes">Notes</h2>

<div class="footnotes" role="doc-endnotes">
  <ol>
    <li id="fn:1">
      <p>Haramoto, Matsumoto, Nishimura, Panneton, L’Ecuyer, “Efficient Jump Ahead for F<sub>2</sub>-Linear Random Number Generators”, <em>INFORMS Journal on Computing</em> 20(3), Summer 2008. <a href="#fnref:1" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:2">
      <p>Vigna, S., “Further scramblings of Marsaglia’s xorshift generators”, <em>Journal of Computational and Applied Mathematics</em> 315 (2017). <a href="#fnref:2" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:3">
      <p>Blackman, Vigna, “Scrambled Linear Pseudorandom Number Generators”, 2019. <a href="#fnref:3" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:4">
      <p>Salmon, John K., Mark A. Moraes, Ron O. Dror, and David E. Shaw. “Parallel random numbers: as easy as 1, 2, 3.” In <em>Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis</em>, pp. 1-12. 2011. <a href="#fnref:4" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:5">
      <p>L’Ecuyer, Simard, Chen, Kelton, “An Object-Oriented Random-Number Package with Many Long Streams and Substreams”, <em>Operations Research</em> 50(6), 2002. <a href="#fnref:5" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:6">
      <p>“<em>x</em> is odd” means that <em>x</em> is an integer and not divisible by 2.  This is true if <em>x</em> − 2*floor(<em>x</em>/2) equals 1, or if <em>x</em> is an integer and the least significant bit of abs(<em>x</em>) is 1. <a href="#fnref:6" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
    <li id="fn:7">
      <p>Brown, F., “Random Number Generation with Arbitrary Strides”, <em>Transactions of the American Nuclear Society</em> Nov. 1994. <a href="#fnref:7" class="reversefootnote" role="doc-backlink">&#8617;</a></p>
    </li>
  </ol>
</div>
</div><nav id="navigation"><ul>
<li><a href="/">Back to start site.</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io">This site's repository (source code)</a>
<li><a href="https://github.com/peteroupc/peteroupc.github.io/issues">Post an issue or comment</a></ul>

<div class="noprint">
<p>
<a href="//x.com/intent/post?text=Notes+on+Jumping+PRNGs+Ahead&url=https%3A%2F%2Fpeteroupc.github.io%2Fjump.html">Share via X (Twitter)</a>, <a href="//www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fpeteroupc.github.io%2Fjump.html">Share via Facebook</a>, <a href="//news.ycombinator.com/submitlink?u=https%3A%2F%2Fpeteroupc.github.io%2Fjump.html&t=Notes+on+Jumping+PRNGs+Ahead">Share via Hacker News</a>, <a href="//www.reddit.com/submit?url=https%3A%2F%2Fpeteroupc.github.io%2Fjump.html&title=Notes+on+Jumping+PRNGs+Ahead">Share via Reddit</a>
</p>
</div>
<p style='font-size:120%;font-weight:bold'><a href='https://peteroupc.github.io/jump.pdf'>Download a PDF of this page</a></p><p>Of interest to the computer graphics and music community:</p><ul><li><a href='https://peteroupc.github.io/graphics.html'><b>Graphics for classic-style game development</b></a>.<li><a href='https://peteroupc.github.io/graphics.html#Building_a_Public_Domain_music_synthesis_library_and_instrument_banks'><b>MIDI music synthesis for classic-style games and apps</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper'><b>Tileable wallpapers with limited colors and resolution</b></a>.<li><a href='https://peteroupc.github.io/graphicsapi.html'><b>Lean programming interfaces for classic graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/uielements.html'><b>Traditional user-interface graphics</b></a>.<li><a href='https://peteroupc.github.io/classic-wallpaper/docs/pixeltovector.html'><b>Converting images to vector graphics</b></a>.</ul><p>Open questions for math and probability experts:</p><ul><li><a href='https://peteroupc.github.io/requests.html'><b>Requests and open questions</b></a>.<li><a href='https://peteroupc.github.io/bernreq.html'><b>Open questions on the Bernoulli factory problem (the new-coins-from-old problem)</b></a>.<li><a href='https://peteroupc.github.io/requestsother.html'><b>Other open questions on probability</b></a>.<li><a href='https://peteroupc.github.io/sampling.html'><b>The sampling problem</b></a>.</ul></nav></body></html>