Xorshift Generators: Appendix - Alan Zucconi
Xorshift Generators: Appendix
Aug 15, 2026
in Maths
This page provide technical information and list of maximal triplets for xorshift generators, and it serve as an appendix for the main article titled Xorshift Generators and video documentary.
Table of Contents
Xorshift Generators<br>Marsaglia’s Companion Block Matrices<br>Other techniques<br>Bibliography
Xorshift Generators
Proposed by Marsaglia in 2003 in "Xorshift RNG’s"
Only 8, 16, 32, and 64 bits are typically natively possible on modern architectures
🟰 Shift matrices
xorshift (n bits, 2 shifts)
Canonical tuples are maximal tuples where
There are half as many canonical tuples as there are maximal tuples, because:
If is maximal, then is also maximal
cannot be maximal
There are possible tuples
uint32_t x;<br>uint32_t next(void)<br>x ^= x > b;<br>return x;
(1)
Bits<br>All tuples<br>Maximal tuples8 49016 225032 961064 39692<br>(7, 9)<br>xorshift64 9690252128 161294256 650250512 261121181024 1046529162048 4190209564096 16769025768192 67092481≤190Maximal tuples of monolithic xorshift generators with 2 shifts
✏️ Correction
In his original paper, Marsaglia included (9, 5, 1) as a maximal triplet for xorshift32. That is likely a typo, as the actual maximal triplet is (9, 5, 14).
xorshift (n bits, 3 shifts)
Canonical triplets are maximal triplets where
There are half as many canonical triplets as there are maximal triplets, because:
If is maximal, then is also maximal
cannot be maximal
There are possible triplets
There are possible triplets with
uint32_t x;<br>uint32_t next(void)<br>x ^= x > b;<br>x ^= x
(2)
🟰 Marsaglia’s xorshift32
Using Marsaglia’s triplet (13, 17, 5):
🟰 Marsaglia’s xorshift64
Using Marsaglia’s triplet (13, 7, 17):
Bits<br>32-bit blocks<br>All triplets<br>Maximal tripletsAll canonical triplets (a<br>Maximal canonical triplets<br>8 –343241471216 –33756015753032 129791162<br>(13, 17, 5)<br>xorshift32 144158164 2250047550<br>(13, 7, 17)<br>xorshift64 1230392759638573751022424175511128 420483832144101612710721605401967926361997199131819266967871336034656951680224711089567535455199192678256 816581375759482581753797288923639903688411778767344232010324617591011816179999505935211432435511340221560175670138412561818871315628017599657841613714733751941635650575970844814893146232119044557407105954801510990223916538548363998269512 16133432831297386658585514869544171601030073343679904079167185761819010937525902948893751295160819223648543411021116400472055164020260917119390421302543991952167221302111711354401508307351772070422347428927520281734673592601473623397065375586821982625752934176824451217663502642253146872513280025510082399596882547219992984483226573856191745322865828153726686427642735647570363209954392851889628716917375811363580581754056892829796597983930963978693274654896030881974079650744405271993253799231973242271108502486130095542511024 321070599167114630534776319573151280402092240639⏳1045302399⏳2048 64857735782345227842865838072261394096 128686691573751790210343261941758951058192 256549554511871⏳274743709695⏳Maximal triplets of monolithic xorshift generators with 3 shifts
A maximal triplet is also maximal for the following 8 variants:
ACodeXx^= x > b; x ^= x x^= x >> a; x ^= x > c;x^= x > b; x ^= x x^= x >> c; x ^= x > a;x^= x > b;x^= x >> a; x ^= x >> c; x ^= x x^= x >> b; x ^= x x^= x > a; x ^= x xorshift (n bits) variants, as classified by Vigna (A column) and Panneton and L’Ecuyer (X column). Table from this paper.
📚 Properties of single-word xorshifts
The three shifts cannot all be left shifts, or right shifts (Proposition 4.1)
If is a maximal triplet, it is also maximal for any of those 8 xorshift variants (Proposition 4.4), because all of their matrix forms are similar
If is maximal, then is also maximal:
(3)
This is because their respective transformation matrices are the transposes of each other. Transposing a matrix does not change its characteristic polynomial.
A triplet of the kind cannot be maximal:
(4)
This is true because the transition matrix would collapse into:
When a matrix is palindromic (i.e.: ), its characteristic polynomial becomes self-reciprocal (which means that its coefficients read exactly the same way forward and backwards). This makes it non-primitive, hence unable to achieve maximal period.
For a triplet to be maximal, , , , and have to be setwise coprime:
(5)
This means they cannot share any prime factor. When is a power of 2, its only prime factor is 2, and this property simply means that at least one among , , and has to be odd (otherwise ).
❓ Open conjectures
The following properties are only conjectures, but likely true as were tested all values calculated so far:
When is even, must be odd:
(6)
The proposed mechanism for this conjecture is that when and are even, then for every odd . If that happens, then all the odd-degree terms of the characteristic polynomial vanish (because they are linked directly to through Newton’s identities). An even-degree term-only...