蒲公英是一个适用于模拟、测试、统计和数据结构算法的高性能非加密随机数生成器。它具有128位的态，周期长度为2¹²⁸ - 1。

示例

use dandelion::Rng;
let mut rng = Rng::from_u64(0);
let x = rng.u64();
let y = rng.between_u64(1, 6);
let z = rng.f64();

算法

蒲公英随机数生成器的核心包括两部分：状态转换函数 F: (u64, u64) -> (u64, u64) 和输出函数 G: (u64, u64) -> u64，其中第k个输出是

G(F(F( ... F(x₀, y₀) ... )))
  \________/
   k times

其中初始状态为 (x₀, y₀)。

状态转换函数 F 定义为

F(x, y) = (y ^ shr(y, 19), x ^ ror(y, 7))

输出函数 G 定义为

G(x, y) = y + ((x * x) ^ ((x * x) >> 64))

其中 x 和 y 是 u64，我们使用了一个 (u64, u64) -> u128 全乘法。我们进一步要求状态不能全为零，即 (x, y) ≠ (0, 0)

关于这些函数，有两点需要注意。首先，F 可以被视为作用在 128 位向量空间 F₂¹²⁸ 上的可逆线性变换，即 F 是 GL(128, F₂) 的一个元素。其次，G 可以被视为 F₂¹²⁸ / { 0 } 上的一个排列，然后进行截断。

状态转换函数的周期

我们将证明状态转换函数的周期为 2¹²⁸ - 1。我们可以在 GL(128, F₂) 中的二进制矩阵上进行必要的计算。设 A 为表示我们的转换的二进制矩阵。那么，只需要证明

pow(A, 2¹²⁸ - 1) = I

和

pow(A, (2¹²⁸ - 1) / p) ≠ I

对于 2¹²⁸ - 1 的所有素数因子 p，其中 I 是单位矩阵。我们可以在 O(log(n)) 时间内计算 pow(A, n)，因此这些计算是可行的。实际上，检查等价的 pow(A, 2¹²⁸) = A 对于第一个条件要快一些。

2¹²⁸ - 1 =
    (2¹ + 1)
    * (2² + 1)
    * (2⁴ + 1)
    * (2⁸ + 1)
    * (2¹⁶ + 1)
    * (2³² + 1)
    * (2⁶⁴ + 1)

2¹²⁸ - 1 =
    3
    * 5
    * 17
    * 257
    * 65_537
    * 641
    * 6_700_417
    * 274_177
    * 67_280_421_310_721

(x, y) ⇒ (y ^ shr(y, α), x ^ ror(y, β))

α=19 β=7
α=29 β=23 
α=33 β=29 

(x, y) ⇒ (y + H(x), x)