0

の特定の実装についてrand、初期シードとこれまでの呼び出し回数を指定して、シーケンス内の次の番号を効率的に生成することは可能randですか?

私が望むのはrand、シミュレーションでノードに時間オフセットを提供するために使用することです。各ノードは、その一意の ID でシードし、の出力を使用randして、シミュレーションの遅延にジッターを提供します。衝突を測定するために、各ノードが他のノードの次の遅延を計算できるようにしたいと考えています。任意のノードの初期シードにアクセスでき、その回数randが呼び出されました。

n + 1次の値を取得するために時間をシードしてループする必要はありません。の一般的なLinux実装でも可能randですか？

4

1 に答える 1

1

glibc の乱数ジェネレーターは線形合同ジェネレーターであり、x_{n+1} = a * x_{n} + b mod m の形式のジェネレーターです。a、b、および m を適切に選択するには、それで十分な場合があります。2つ以上を組み合わせると、品質が向上します。

このようなシーケンスを先にスキップするのはかなり簡単です。x_{n+k} = a^{k} * x_{n} + b * (a^{k} - 1)/(a - 1) mod m。m を法として数値をべき乗することは、数値のビット数、つまり O(log(数値)) に比例します。乗法逆数を取るには、拡張ユークリッド アルゴリズムを使用するだけです。後者は一度だけ行う必要があります。

于 2012-11-19T23:14:11.760 に答える