如何从单个种子廉价地产生无限可分割的非冲突数字流？

Question

我需要一个函数split : Word64 -> (Word64, Word64)，可以接受任何 Word64 并将其拆分为两个不同的 Word64，这样我就可以继续以任意顺序拆分子代和孙代，同时避免冲突。也就是说，对于sa, sb种子的任何一对连续分裂（例如sa = fst.split.fst.split$ seed），sa必须与sb>99.99% 的几率不同。

我考虑过使用配对函数，但这会使孩子比父母大，所以，在几次分割之后，会出现整数溢出。我需要的东西基本上以半随机的方式将可能的 Word64 位空间上的任何值发送到其他两个值。另外，我需要它尽可能快速和简单。指令越少越好。这可能是我错过的一个非常愚蠢的计算。

这里可以使用什么？

免责声明：我以前也问过类似的问题，但现在我终于对问题有了更好的理解，并且确切地知道我需要什么。

Answer 1

不幸的是，我无法证明以下内容的任何统计属性，因此这只是一种启发式方法。它基于伪随机序列生成器的xorshift系列，众所周知，该系列的速度非常快。

考虑xorshift* 算法，如 C 所示：

#include <stdint.h>

uint64_t x; /* The state must be seeded with a nonzero value. */

uint64_t xorshift64star(void) {
    x ^= x >> 12; // a
    x ^= x << 25; // b
    x ^= x >> 27; // c
    return x * UINT64_C(2685821657736338717);
}

维基百科条目中的解释指出：

xorshift* 生成器采用 xorshift 生成器，并将可逆乘法（对字大小取模）应用于其输出作为非线性变换。

我建议的启发式算法是：

• 给头节点一些非零值x。

• 对于每个拆分，运行上面的算法，并x在开始时将其作为父级的值。但是，对于返回值

  • 对于左孩子，将最后一行替换为return x;（本质上是经典xorshift算法）

  • 对于右孩子，使用如上所述的最后一行。

在任何节点u处，采用任意两条不同的后代路径通向不同的v和w。然后要么

• v是w的后代，因此至少对w的值应用 xorshift 或 xorshift* 一次以获得v 的值。

• w是v的后代，可以提出相同的论点。

• 两个节点都不是另一个节点的父节点。在这种情况下，沿着从u到v和w的最低共同祖先（可能是u本身）的路径至少进行了一次非线性变换。