September 12th, 2017 This is just a brief summary of properties I plan on referencing in some future posts. I’m using non-standard notation in an attempt to be accessible to programmers not familar number theory style notation. I’m using sequence instead of generator to distance myself from the particular case of random number generation. Fundamental linear congruential sequences In 1972 George Marsaglia1 defines a fundamental sequence as the follow recurrence relation and initial value: \[\begin{eqnarray} y_{i+1} & = & \left(a~y_{i} + 1 \right) \bmod m \label{flcs} \\ y_0 & = & 0 \nonumber \end{eqnarray}\] so the sequence is: \[\left(0,~1,~a+1,~a^2+a+1, \ldots \right)\] Each element is a finite geometric series, so we can also write a closed form equation: \[\begin{equation} y_i = \sum _{n=0}^{i-1} a^n = \frac{a^i-1}{a-1} \bmod m \label{flcsc} \end{equation}\] If we look at the elements which follow some $y_i$ we have: \[\left(a y_i+1,~a^2 y_i+a+1,~a^3 y_i+a^2+a+1, \ldots \right)\] so we can directly express jumping ahead by $k$ elements: \[\begin{equation} y_{i+k} = a^k y_i + \sum _{n=0}^{k-1} a^n = \left(a^k y_i + \frac{a^k-1}{a-1} \right) \bmod m \label{yi_skip} \end{equation}\] I will only seriously consider full-period (length $m$) sequences which require following to be true2: $a-1$ is divisible by all prime factors of $m$ $a-1$ is divisible by 4 if $m$ is divisible by 4 So for power-of-two modulus this implies (a & 3) == 1 (SEE BELOW), where & denotes a bitwise and operation. Defining an ordered set of integers: \[\mathbb{Z}_m = \left\{0,1,2, \ldots, m-1\right\}\] We have some redundant direct implications of being full-period: the first $m$ elements are a permutation of $ \mathbb{Z}_m $ All subsequences of $m$ elements visit each element of $ \mathbb{Z}_m $ exactly once $y_{\left(i \bmod m\right)} = y_i $ Let’s also note than relaxing the defination of $y_0$ to be settable to any element of $ \mathbb{Z}_m $ doesn’t change anything. Logically we’d just be renaming our element index $i$. Linear congruential sequences LCS The sequence is defined as: \[\begin{eqnarray} x_{i+1} & = & \left(a~x_{i} + b\right) \bmod m \label{lcs} \\ x_0 & = & 0 \label{x0} \end{eqnarray}\] Requiring $x_0$ to be zero is non-standard, but the logic is the same as for the fundamental sequence. For it to be full-period the same contraints apply to $a$ and additionally $b$ must be coprime with $m$, explicitly: $\gcd\left(b,m\right)=1$, which for power-of-two modulus mean it must simply be odd. We can also define closed form expressions for a given element $x_i$ and for an offset $x_{i+k}$: \[\begin{eqnarray} x_i & = & \left(a^i x_0 + b \sum _{n=0}^{i-1} a^n \right) \bmod m \nonumber \\ & = & \left(a^i x_0 + \frac{a^i-1}{a-1}b \right) \bmod m \\ & = & \left(\frac{a^i-1}{a-1}b \right) \label{lcs_x1} \bmod m \\ \nonumber \\ x_{i+k} & = & \left(a^k x_i + \frac{a^k-1}{a-1}b \right) \bmod m \label{skip} \end{eqnarray}\] Where $\eqref{lcs_x1}$ is reduced using my local requirement $\eqref{x0}$. Marsaglia1 showed that the two sequences are simply related3: \[\begin{eqnarray} x_i & = & \left(\alpha~y_{i} + \beta\right) \bmod m \nonumber \\ \alpha & = & \left(x_0\left(a-1\right)+b\right) \bmod m \nonumber \\ \beta & = & x_0 \bmod m \nonumber \end{eqnarray}\] which given our contraint $\eqref{x0}$ reduces to (or seen directly from $\eqref{flcsc}$ and $\eqref{lcs_x1}$): \[\begin{eqnarray} x_i & = & \left(b~y_{i}\right) \bmod m \label{yi2xi} \\ y_i & = & \left(b^{-1}~x_{i}\right) \bmod m \nonumber \end{eqnarray}\] The constraint on full-period $b$ insures that it has a multiplicative inverse (standard abuse of notation denoted as $b^{-1}$) so we can solve both ways as per the second equation above. For random number generation this relation implies that the multiplicative constant $a$ dominates the statistical properties of sequences. Melissa O’Neill’s PCG generator4 uses this feature to provide independent streams of generators by having a different additive value $b$ per stream. For sequences in general each $b$ provides a unique permutation. Another way to look at these full-period sequences is that they are one-to-one correspondences or bijections and therefore have inverse functions, so the multiplier $a$ has a multiplicative inverse as well. Taking $\eqref{flcs}$, renaming indices and inverting: \[\begin{eqnarray*} y_{i-1} & = & a^{-1}\left(y_{i} - 1 \right) \bmod m \\ & = & \left(a^{-1}~y_{i} - a^{-1} \right) \bmod m \end{eqnarray*}\] So there are no fundamental sequences which are simply reversed order of another. For the standard sequence we have: \[\begin{eqnarray*} x_{i-1} & = & \left(a^{-1}x_{i} - a^{-1}b \right) \bmod m \end{eqnarray*}\] Which shows that multplicative constants $a$ and $a^{-1}$ are equivalent in terms of choice for statistical properties. If we specify a set of LCS constants as $\left(a,~b\right)$ and have two sequences $\left(a_0,~b_0\right)$ and $\left(a_1,~b_1\right)$ then they are simply reversed ordered if these conditions hold: $ \left(a_0~a_1 \right) \bmod m = 1 $ $ \left(a_0~b_1 - b_0\right) \bmod m = 0 $ Back to our skip $k$ elements equation $\eqref{skip}$ we can see it forms a sequence with constants $\left(a^k, ~\frac{a^k-1}{a-1}b \right)$, but it will only be full-period if $k$ and $m$ are coprimes. It’s probably worth noting that move backwards by $n$ elements is equivalent to a forward by $m-n$. Block properties This is brushstrokes without proof or much justification. Assuming most people aren’t really interested in seeing either. If we take a fundamental sequence and weaking the constraint on $a$ to being coprime with $m$ then we have a periodic sequence, which includes full-period sequences. First we can define the multiplicative order5 of $a$ as the smallest positive integer $t$ such that $\left(a^t\right)\bmod m = 1$ which is commonly written as: \[t = \text{ord}_m\left(a\right)\] Next we define $c$ as the translating constant of $a$ as $c = \frac{a^t-1}{a-1}$ (SEE: $\eqref{flcsc}$) and final the additive order of $c$ as the smallest positive integer $r$ such that $\left(cr\right)\bmod m=0$ which reduces to: \[r=\frac{m}{\gcd\left(c,m\right)}\] Given these values then a periodic fundamental sequence contains blocks of subsequences. A block contains $t$ elements: \[\left\{B\right\} = \left\{y_0,~y_1,\ldots,~y_{t-1}\right\}\] and a sequence is a series of translated blocks: \[\left\{B\right\}, \left\{B+c\right\}, \left\{B+2c\right\}, \ldots\] The translated blocks can be seen directly from $\eqref{yi_skip}$ and the defination of $c$: \[\begin{eqnarray*} y_{i+t} & = & \left(a^t + a^{t-1} + \ldots + 1\right) \bmod m \\ & = & \left(a^t + c\right) \bmod m \end{eqnarray*}\] In the LCS case from $\eqref{yi2xi}$ we have: \[\left\{B\right\}, \left\{B+bc\right\}, \left\{B+2bc\right\}, \ldots\] power-of-two modulus For pragmatic reasons having a power-of-two modulus $\left(m=2^\beta\right)$ is the most interesting case. Let’s recap $a$ from a programmer viewpoint: If bit zero is set then the sequence is periodic (it’s odd so a coprime). If also bit one is clear then the sequence is full period: (a&3) == 1 RNG papers also recommend bit two be set: (a&7) == 5 The last is because of the block structure. Sticking to full-period then if $a=k~2^\alpha+1$ for some odd $k$ and $\alpha \ge 2$, or if ctz is a function that counts trailing zeroes then alpha = ctz(a-1), then our block properties are: multiplicative order $t = 2^{\beta-\alpha}$ 1<<(beta-alpha) fundamental translation $c = t+2^{\beta-1}$ t|(1<<(beta-1)) translatation constant $bc$ additive order $r = 2^\alpha$ 1<<alpha period $tr = 2^\beta$ So the reason for the (a&7) == 5 recommendation is so we have the fewest number of blocks, which in that case is four. (The values of the last two bits are fixed, so the smallest possible alpha value is two). Might as well skim the periodic but not full-period case. The last two bits are set (a&3) == 3 and if $a=k~2^\alpha-1$ for some odd $k$ and $\alpha \ge 2$, or alpha = ctz(~a), then our block properties are: multiplicative order $t = 2^{\beta-\alpha}$ fundamental translation $c = 2^{\beta-1}$ translatation constant $bc$ additive order $r = 2 $ period $tr = 2^{\beta-\alpha+1}$ number of sequences $2^{\alpha-1}$ Like the full-period case: smallest alpha is two and so the largest possible block size is $2^{\beta-2}$. A consequence of this block structure (for power-of-two modulus) is: The period of the $n^{th}$ bit is $2^{n+1}$, where zero is the lowest bit. So the lowest bits’ period is two…it simply toggles between one and zero. If we mask off the bottom $n$ bits then we’ll see a sequence of some permutation of \(\left\{0,1,\ldots, 2^n-1\right\}\) with a period of $2^n$. Let’s run with an example of a fundamental sequence, some ugly code that matches the math defs: static const uint32_t a = 2891336453; uint32_t xi = 0; static inline uint32_t next() { xi = a*xi + 1 ; return xi; } Where the 32-bit constant $a$ was simply grabbed from L’Ecuyer’s table paper6. If we examine 32 values starting from $i=1$ then we have: 00000001 ac564b06 e1ae391f 778d329c 83fdb10d 1d314442 4721ab4b 30095178 a95cbf59 8ec4cfbe e488b8b7 86433894 c29b76e5 25cc697a 06e0cd63 81d203f0 a2e163b1 a011cd76 a52e954f 1c310f8c 358b51bd 4e28f7b2 5529fc7b 6c1bf768 4af74d09 d76c242e f32a2ee7 112a9784 6690a195 c437ceea e9519893 7bad0be0 and isolating the sequence of bits in positions 0-4 give: 0 10101010101010101010101010101010 1 01100110011001100110011001100110 2 01111000011110000111100001111000 3 00111011110001000011101111000100 4 00110001111101011100111000001010 The bolded zeroes show the first element of the cycle for that bit position. These are always zero since since by defination $f_0 = 0$ and we are back to that position every $2^{n+1}$ steps. And the bottom $n$ bits for 1-5 (2 digit hex) and starting from zero this time: mask : sequence 01 : 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 00 01 03 : 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 07 : 00 01 06 07 04 05 02 03 00 01 06 07 04 05 02 03 00 01 06 07 04 05 02 03 00 01 06 07 04 05 02 03 0F : 00 01 06 0f 0c 0d 02 0b 08 09 0e 07 04 05 0a 03 00 01 06 0f 0c 0d 02 0b 08 09 0e 07 04 05 0a 03 1F : 00 01 06 1f 1c 0d 02 0b 18 19 1e 17 14 05 1a 03 10 11 16 0f 0c 1d 12 1b 08 09 0e 07 04 15 0a 13 Our $a$ is 2891336453 which in binary is 10101100010101100100101100000101, so if mask=(1<<n)-1, then effective update for the bottom $n$ bits, when it’s one or two is: xi = (xi+1) & mask and this is the case for all full-period sequence due the the requirement on these bits. This constant also has the recommended bit 3 set and the rest of the lowest byte is zero, so the effective update for low bit window sizes 3-8 is xi = (5*xi+1) & mask. Since the block structure is also present in all of these low-bit windows, then having that recommended bit set ensures that they all have an alpha of two and the largest possible block size which breaks the period into four blocks. Repeating the n-bit window from above (from n=3) with block boundaries indicated and adding the first two blocks of 6 bit window. The translations are $2^{n-2}+2^{n-1}$ or 3<<(n-2), which in hex are: 06,0c,18,30: |00 01|06 07|04 05|02 03| |00 01 06 0f|0c 0d 02 0b|08 09 0e 07|04 05 0a 03| |00 01 06 1f 1c 0d 02 0b|18 19 1e 17 14 05 1a 03|10 11 16 0f 0c 1d 12 1b|08 09 0e 07 04 15 0a 13| |00 01 06 1f 1c 0d 02 0b 38 19 3e 37 14 25 3a 23|30 31 36 0f 0c 3d 32 3b 28 09 2e 27 04 15 2a 13| References and Footnotes “Linear Congruential Sequences”, George Marsaglia, 1972 (not publiclly available) ↩ ↩2 “Random number generators”, T.E. Hull and A.R. Dobell, 1962 (PDF) ↩ Also holds for Lehmer sequences or more commonly multiplicative linear congruential generators. Note for this sequence we cannot choose to have $x_0$ be zero. ↩ “pgc-random.org”, (website) ↩ “Multiplicative Order” (Wikipedia) (MathWorld) ↩ “Tables of linear congruential generators of different sizes and good lattice structure”, Pierre L’Ecuyer, 1999 (PDF) ↩ Comments math (32) random (16) , sequence (6) , permutation (2)