我希望創(chuàng)建一個確定性數(shù)字生成函數(shù)，其中輸入數(shù)字將始終生成相同的數(shù)字，但沒有兩個數(shù)字最終會生成相同的結(jié)果。例如：1 -> 32 -> 53 -> 44 -> 25 -> 1但是，我需要它適用于可以由特定數(shù)據(jù)類型（例如 int64）表示的所有數(shù)字。這感覺像是應(yīng)該非常簡單或完全不可能的事情。是否有一些隨機(jī)數(shù)生成方案可以保證這種分布，而我不必創(chuàng)建一個包含所有可能數(shù)字的數(shù)組、隨機(jī)排序，然后使用索引（同時讓我耗盡內(nèi)存）？
2 回答
繁花如伊
TA貢獻(xiàn)2012條經(jīng)驗 獲得超12個贊
您需要的轉(zhuǎn)換公式是：
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它在所需范圍內(nèi)，s是一個簡單的移位并且m應(yīng)該與互質(zhì)n。Coprime 只是意味著n并且m不應(yīng)該共享任何共同因素。因為n是 2^64 它唯一的因素是數(shù)字2- 所以m基本上不應(yīng)該是偶數(shù)（即不能被 2 整除）：
所以對于uint64范圍：
這可能看起來很神奇，但您可以說服自己它適用于uint16：
https://go.dev/play/p/EKB6SH3-SGu
（因為uint64需要相當(dāng)多的資源才能運行 :-)
更新：
對于帶符號的數(shù)字（即int64），邏輯沒有什么不同。因為我們知道我們有一個獨特的一對一映射，uint64其中一種方法就是將輸入和輸出從 轉(zhuǎn)換為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
鴻蒙傳說
TA貢獻(xiàn)1865條經(jīng)驗 獲得超7個贊
要添加到colm.anseo答案，這種映射也稱為Linear congruential generator。
X n+1 = (aX n + c) mod m
當(dāng) c ≠ 0 時，對于所有種子值，正確選擇的參數(shù)允許一個等于 m 的周期。當(dāng)且僅當(dāng)：
m和c互質(zhì)，
a-1 可被 m 的所有質(zhì)因數(shù)整除，
如果 m 可以被 4 整除，則 a-1 可以被 4 整除。
這三個要求被稱為 Hull-Dobell 定理。
對于 64 位 LCG，Knuth 的 a=6364136223846793005 和 c=1442695040888963407 看起來不錯。
請注意，LCG 映射是一對一的，它將整個 [0...2 64 -1] 區(qū)域映射到自身。如果你愿意，你可以反轉(zhuǎn)它。作為RNG，它具有獨特的跳躍能力。
- 2 回答
- 0 關(guān)注
- 112 瀏覽
添加回答
舉報
0/150
提交
取消