从另一个没有重复的确定性 int 生成

Question

我希望创建一个确定性数字生成函数，其中输入数字将始终生成相同的数字，但没有两个数字最终会生成相同的结果。例如：1 -> 32 -> 53 -> 44 -> 25 -> 1但是，我需要它适用于可以由特定数据类型（例如 int64）表示的所有数字。这感觉像是应该非常简单或完全不可能的事情。是否有一些随机数生成方案可以保证这种分布，而我不必创建一个包含所有可能数字的数组、随机排序，然后使用索引（同时让我耗尽内存）？

Answer 1

您需要的转换公式是：

f(P) = (mP + s) mod n

// n = range - so for uint64 2^64

// s < range i.e. < 2^64

// m = must be coprime with n

这是仿射密码中使用的模块化算法。

确保mod它在所需范围内，s是一个简单的移位并且m应该与互质n。Coprime 只是意味着n并且m不应该共享任何共同因素。因为n是 2^64 它唯一的因素是数字2- 所以m基本上不应该是偶数（即不能被 2 整除）：

所以对于uint64范围：

这可能看起来很神奇，但您可以说服自己它适用于uint16：

https://go.dev/play/p/EKB6SH3-SGu

（因为uint64需要相当多的资源才能运行 :-)

---

更新：

对于带符号的数字（即int64），逻辑没有什么不同。因为我们知道我们有一个独特的一对一映射，uint64其中一种方法就是将输入和输出从 转换为uint64，int64反之亦然：

// original unsigned version

func transform(p uint64) uint64 {

    return m*p + s

}

func signedTransform(p int64) int64 {

    return int64(transform(uint64(p)))

}

又是一个int16证明没有碰撞的例子：

https://go.dev/play/p/Fkw5FLMK0Fu

Answer 2

要添加到colm.anseo答案，这种映射也称为Linear congruential generator。

X _n+1 = (aX _n + c) mod m

当 c ≠ 0 时，对于所有种子值，正确选择的参数允许一个等于 m 的周期。当且仅当：

• m和c互质，

• a-1 可被 m 的所有质因数整除，

• 如果 m 可以被 4 整除，则 a-1 可以被 4 整除。

这三个要求被称为 Hull-Dobell 定理。

对于 64 位 LCG，Knuth 的 a=6364136223846793005 和 c=1442695040888963407 看起来不错。

请注意，LCG 映射是一对一的，它将整个 [0...2 ⁶⁴ -1] 区域映射到自身。如果你愿意，你可以反转它。作为RNG，它具有独特的跳跃能力。