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

Question

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

例如：

1 -> 3
2 -> 5
3 -> 4
4 -> 2
5 -> 1

但是我需要它来处理所有可以由特定数据类型表示的数字，例如一个 int64.

这感觉应该是非常简单的，或者完全不可能的。是否有一些随机数生成方案可以保证这种分布，而我不必创建一个包含所有可能数字的数组、随机排序，然后使用索引（同时让我运行内存不足）？

非常感谢 F

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

这是modular arithmetic as used in the Affine cipher。

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

因此对于 uint64 范围：

var (
    m = uint64(39293)    // some non-even number
    s = uint64(75321908) // some random number below 2^64
)

func transform(p uint64) uint64 {
    return p*m + s // implicitly mod'ed 2^64 by the type's size
}

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

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

（因为 uint64 会占用相当多的资源运行 :-)

更新:

对于带符号的数字（即 int64），逻辑没有什么不同。因为我们知道我们有一个独特的 one-to-one 与 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 answer, this kind of mapping is also known as Linear congruential generator。

X_n+1 = (aX_n+c) mod m

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

m和c互质,
a-1能被m的所有质因数整除，
如果m能被4整除，a-1能被4整除

这三个要求被称为赫尔-多贝尔定理。

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

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

的独特能力

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

Generating a deterministic int from another with no duplicates

go

random

random-seed