go - 从另一个没有重复的确定性 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在 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)，逻辑没有什么不同。因为我们知道我们与 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