生成下一個僞隨機值，給定種子和偏移

Question

對於給定的實現rand，給定初始種子和到目前爲止調用rand的次數是否可能有效地生成序列中的下一個數字？

我想要的是使用rand爲模擬中的節點提供時間偏移。每個節點將播種其唯一的ID，並使用rand的輸出在模擬延遲中提供抖動。我希望每個節點都能夠計算下一個延遲，以便其他節點測量衝突。我可以訪問任何節點的初始種子，並調用rand的次數。

我想避免必須播種和循環n + 1次以獲得下一個值。我想用rand的通用linux實現甚至可能嗎？

Answer 1

glibc中的隨機數發生器是線性同餘發生器，形式爲 x_ {n + 1} = a * x_ {n} + b mod m的發生器。爲了正確選擇a，b和m，它可能就足夠了。兩個或更多的組合可以提高質量。

在這樣的順序中很容易跳過。 x_ {n + k} = a^{k} * x_ {n} + b *（a^{k} -1）/（a-1）mod m。 將數字提高到功率mod m的數字位數是線性的，即O（log（number））。採取乘法逆運算，您只需使用擴展的歐幾里得算法。你只需要做後者一次。