MacOS は、stdlib で文書化されていない rand() 関数を提供します。シードなしのままにしておくと、最初に出力される値は 16807、282475249、1622650073、984943658、および 1144108930 になります。すばやく検索すると、このシーケンスが次の式を反復する非常に基本的な LCG 乱数ジェネレーターに対応していることがわかります。
<ブロック引用>x n +1 =7 · x n (mod 2 − 1)
この RNG の状態は 1 つの 32 ビット整数の値によって完全に記述されるため、その期間はそれほど長くはありません。正確には、2 − 2 回の反復ごとに繰り返され、1 から 2 − 2 までのすべての値が出力されます。
標準はないと思います Linux のすべてのバージョンでの rand() の実装ですが、よく使用される glibc の rand() 関数があります。単一の 32 ビット状態変数の代わりに、これは 1000 ビットを超えるプールを使用します。これは、すべての意図と目的に対して、完全に繰り返されるシーケンスを生成することは決してありません。繰り返しますが、この RNG からの最初のいくつかの出力を、最初にシードせずに出力することで、使用しているバージョンをおそらく見つけることができます。 (glibc rand() 関数は、数値 1804289383、846930886、1681692777、1714636915、および 1957747793 を生成します。)
したがって、Linux でより多くの衝突が発生する (MacOS ではほとんどない) 理由は、rand() の Linux バージョンが基本的によりランダムであるためです。
最初は macOS rand() のように聞こえるかもしれませんが、 数字を繰り返さないほうがいいのですが、この量の数字が生成されると、多くの重複が見られることが予想されることに注意してください (実際、約 7 億 9000 万、または (2-1)/e) ）。同様に、番号を順番に反復しても重複は生成されませんが、非常にランダムとは見なされません。だから、Linux rand() 実装はこのテストにあります 真のランダム ソースと見分けがつかないのに対し、macOS rand()
一見驚くように見えるもう 1 つのことは、macOS の rand() 重複をうまく回避できます。ソースコードを見ると、実装は次のようになっています:
/*
* Compute x = (7^5 * x) mod (2^31 - 1)
* without overflowing 31 bits:
* (2^31 - 1) = 127773 * (7^5) + 2836
* From "Random number generators: good ones are hard to find",
* Park and Miller, Communications of the ACM, vol. 31, no. 10,
* October 1988, p. 1195.
*/
long hi, lo, x;
/* Can't be initialized with 0, so use another value. */
if (*ctx == 0)
*ctx = 123459876;
hi = *ctx / 127773;
lo = *ctx % 127773;
x = 16807 * lo - 2836 * hi;
if (x < 0)
x += 0x7fffffff;
return ((*ctx = x) % ((unsigned long) RAND_MAX + 1));
これは実際、1 から RAND_MAX までのすべての数値になります。 、包括的、正確に 1 回、シーケンスが再び繰り返されます。次の状態は乗算に基づいているため、状態がゼロになることはありません (または、将来のすべての状態もゼロになります)。したがって、表示される繰り返し数は最初のものであり、0 は決して返されないものです。
Apple は、少なくとも macOS (または OS X) が存在する限り、ドキュメントと例でより優れた乱数ジェネレーターの使用を促進してきたため、rand() の品質は はおそらく重要ではないと考えられており、利用可能な最も単純な疑似乱数ジェネレーターの 1 つに固執しているだけです。 (あなたが指摘したように、彼らの rand() arc4random() の使用を推奨するコメントさえあります 代わりに。)
関連する注意事項として、ランダム性のこの (および他の多くの) テストで適切な結果を生成する、私が見つけることができる最も単純な疑似乱数ジェネレーターは xorshift* です:
uint64_t x = *ctx;
x ^= x >> 12;
x ^= x << 25;
x ^= x >> 27;
*ctx = x;
return (x * 0x2545F4914F6CDD1DUL) >> 33;
この実装により、テストでほぼ正確に 7 億 9000 万の重複が発生します。
rand() は C 標準で定義されており、C 標準は使用するアルゴリズムを指定していません。明らかに、Apple は GNU/Linux 実装より劣ったアルゴリズムを使用しています。Linux のアルゴリズムは、テストで真のランダム ソースと区別がつかないのに対し、Apple 実装は数値をシャッフルするだけです。
任意の品質の乱数が必要な場合は、返される数値の品質に少なくともある程度の保証を与えるより優れた PRNG を使用するか、単に /dev/urandom から読み取るかのいずれかです。 または類似。後者は暗号品質の数値を提供しますが、遅いです。単体では遅すぎても /dev/urandom 優れたシードを他のより高速な PRNG に提供できます。
一般に、rand/srand ペアは、結果で下位ビットが上位ビットよりもランダム性が低いため、長い間非推奨と見なされてきました。これはあなたの結果と関係があるかもしれませんし、ないかもしれません。 ）。私の Arch Linux ボックスでは、次のメモがまだ rand(3) の man ページにあります:
The versions of rand() and srand() in the Linux C Library use the same random number generator as random(3) and srandom(3), so the lower-order bits should be as random as the higher-order bits. However, on older rand() implementations, and on current implementations on different systems, the lower-order bits are much less random than the higher-or- der bits. Do not use this function in applications intended to be por- table when good randomness is needed. (Use random(3) instead.)
そのすぐ下の man ページには、実際には、これまでに見た中で最も単純な LC RNG であり、小さな RAND_MAX を持つ、rand と srand の非常に短く、非常に単純な実装例が示されています。 C標準ライブラリにあるものと一致するとは思いません。または、少なくともそうでないことを願っています。
一般に、標準ライブラリから何かを使用する場合は、可能であれば random を使用します (man ページでは、POSIX.1-2001 までさかのぼって POSIX 標準としてリストされていますが、rand は C が標準化される前の標準です)。 .またはさらに良いことに、Numerical Recipes を開いて (またはオンラインで探して)、Knuth を実装してください。それらは非常に簡単で、1 回実行するだけで、最も頻繁に必要となる属性を備えた既知の品質の汎用 RNG を作成できます。