Random Number Generation

2024-12-01 • 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

---

Random Tree Method

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

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

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} = (aX_{n} + c) \text{ 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{align} L_{k+1} = aL_{k}\text{ mod } m \\ R_{k+1} = a^nR_{k}\text{ mod } m \end{align} $$

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^{th}$ sub-sequence, $R^r$ is given with $a^n$ and starting point from the $L$ sequence as $R^r_{0} = L_{r}$. We need to compute $a^r$ and $a^n$

$$ \begin{align} a^{2k} \text{ mod } m = (a^k \text{ mod } m)^2 \text{ mod } m \end{align} $$

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

$$ \begin{align} R^r_{0} = (a^rL_{0}) \text{ mod } m \\ R^r_{i+1} = (a^nR^r_{i}) \text{ mod } m \end{align} $$

This method can be called recursively. The subsequence corresponding to $(R^r_{0}, 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{align} L_{k+1} = a^nL_{k} \text{ mod } m \\ R_{ k + 1 } = aR_{k} \text{ mod } m \end{align} $$