Random Number Generation

Dec 2024 • RNG notes tech

Some info dump while I try to figure out random number generations. No TOC for this page, but here is a tree -L1

.
├── Algorithms
│   ├── CSPRNG.md
│   └── Random Tree - Linear Congruential Algo.md
└── Random Number Generation.md

2 directories, 3 files

Citations for this chunk

- Handling generators based on linear congruential algorithm with random tree method

Random Tree Method

it employs two linear congruential generators $L$ and $R$ that differ in a value for $a$

$\begin{array}{r} L_{k + 1} = a_{L} L_{k} mod m \\ R_{k + 1} = a_{R} L_{k} mod m \end{array}$

This is inline $x^{2}$

Linear Congruential Generator generates a sequence of pseudo-random numbers using discontinuous piecewise linear equation The generator: $X_{n + 1} = (a X_{n} + c) mod m$ where

$m, 0 < m$ is the modulus

$a, 0 < a < m$ is the multiplier

$c, 0 \leq c < m$ is the increment

$X_{0}, 0 \leq X_{0} < m$ is the seed
func linearCongruentialGenerator(X0, m, a, c, N int) []int {
    randNums := make([]int, N)
    randNums[0] = X0
    for i := 1; i < N; i++ {
        randNums[i] = (a * randNums[i - 1] + c) % m
    }
    return randNums
}

In this case, the left generator $L$ with a seed $L_{0}$ has one random sequence. The right generator $R$ with the same seed generates another sequence. We use the right generator for values in computation while the left generator is applied to the values computed by R to obtain the starting points for $R^{0}, R^{1}, \dots$

When a new task is in need for random numbers, the parent generator in this case $L$ creates a new random number in its sequence, which is then used to create a branch using the right generator $R$ whose value is used for computation

When two starting points created between two consecutive values generated by $L$ are close, the two right sequence branches will be highly correlated

Leapfrog Method

This is a variant of random tree method which can be guaranteed not to overlap over a certain period. If $n$ is a sequence required. We define $a_{L}$ and $a_{R}$ as $a$ and $a^{n}$ such that we have

$\begin{array}{r} L_{k + 1} = a L_{k} mod m \\ R_{k + 1} = a^{n} R_{k} mod m \end{array}$

We create $n$ different right generators $R^{0} \dots R^{n - 1}$ from the first $n$ elements of the $L$ generator. The sequence generated by $R^{i}$ consists of $L_{i}$ and the subsequent elements of the sequence.

The sequence generated by $L$ is portioned each having a period of $\frac{P}{n}$ where $P$ is the period of $L$ . Hence each right generator selects a a disjoint sequence from the left generated sequence

For the $r^{t h}$ sub-sequence, $R^{r}$ is given with $a^{n}$ and starting point from the $L$ sequence as $R_{0}^{r} = L_{r}$ . We need to compute $a^{r}$ and $a^{n}$

$\begin{array}{r} a^{2 k} mod m = (a^{k} mod m)^{2} mod m \end{array}$

The sequence generated by $R^{r}$ is defined as

$\begin{array}{r} R_{0}^{r} = (a^{r} L_{0}) mod m \\ R_{i + 1}^{r} = (a^{n} R_{i}^{r}) mod m \end{array}$

This method can be called recursively. The subsequence corresponding to $(R_{0}^{r}, a^{n}, m)$ can be further sub-divided by a second application of leap frog, with a outcome of the subsequence becoming shorter

Modified Leapfrog

When we know the max number $n$ of random variables needed in a sub-sequence but we don't know how many subsequences are required

Here $L_{i * n}, \dots L_{(i + 1) * (n - 1)}$ are contiguous elements. Choosing $n$ as a power of two can lead to long correlations.

$\begin{array}{r} L_{k + 1} = a^{n} L_{k} mod m \\ R_{k + 1} = a R_{k} mod m \end{array}$