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

Question

我希望创建一个确定性数字生成函数，其中输入数字将始终生成相同的数字，但没有两个数字最终会生成相同的结果。

例如：

1 -> 3

2 -> 5

3 -> 4

4 -> 2

5 -> 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 versionfunc transform(p uint64) uint64 {&nbsp; &nbsp; return m*p + s}func signedTransform(p int64) int64 {&nbsp; &nbsp; return int64(transform(uint64(p)))}又是一个int16证明没有碰撞的例子：https://go.dev/play/p/Fkw5FLMK0Fu

Answer 2

要添加到colm.anseo答案，这种映射也称为Linear congruential generator。X&nbsp;n+1&nbsp;= (aX&nbsp;n&nbsp;+ 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&nbsp;64&nbsp;-1] 区域映射到自身。如果你愿意，你可以反转它。作为RNG，它具有独特的跳跃能力。