rand（）：奇妙な振る舞い

Question

私は最初にN/2 0と他の1を持つN要素の配列を生成する必要がある問題の数値シミュレーションを行っています。各反復では、配列はシャッフルされ、次の配列要素は、0または1だけが残るまで前の反復からランダムに選択されます。私は反復回数をT回の試行で記録しています。ランダムな整数を生成するには、私はrand()（考えをhereから得ました）を使ってdiscard-moduloメソッドを使用しています。

#include <iostream> 
#include <ctime>  
#include <cstdlib> 
#include <fstream>  
#include <algorithm> 
#include <array> 

using namespace std; 

//generate random integer between 0 and MAX 
int randomn(int MAX); 

int main() 
{ 
    const int N = 10000; 
    const int T = 100;  //Number of trials 

    srand((unsigned)time(0)); 

    ofstream writefile ("Observation.out"); 

    for (int indexT = 0; indexT < T; indexT++) { 

     //initializing myArray 
     array<bool, N> myArray; 
     array<bool, N> newArray; 

     auto middle = myArray.begin() + myArray.size()/2; 
     fill(myArray.begin(), middle, false); 
     fill(middle, myArray.end(), true); 

     int counterIt = 0; //desired Iteration number 

     for (;;) { 
      int counterF = 0; 
      int randompos = 0; 
      bool savedata = true; 

      //suffling myArray using Fisher–Yates shuffle 
      for (int indexN = N-1; indexN > 0; indexN--) { 
       randompos = randomn(indexN); 
       savedata = myArray[randompos]; 
       myArray[randompos] = myArray[indexN] ; 
       myArray[indexN] = savedata; 
      }   
      //next Iteration 
      for (int indexN = 0; indexN < N; indexN++) { 
       randompos = randomn(N-1); 
       savedata = myArray[randompos]; 
       newArray[indexN] = savedata; 
       if (savedata == false){ 
        counterF += 1; 
       } 
      } 

      copy(begin(newArray), end(newArray), begin(myArray)); 

      //updating Iteration number 
      counterIt += 1; 

      if ((counterF == 0)|| (counterF == N)) { 
       break; 
      } 

     } 

     writefile << indexT+1 <<"\t"<<counterIt <<endl; 
    } 

    writefile.close(); 

    return 0; 
} 

int randomn (int MAX){ 
    int temp; 
    for (;;){ 
     temp = rand(); 
     if (temp < RAND_MAX - RAND_MAX%(MAX+1)) 
      return temp%(MAX+1); 
    } 
} 

出力はかなり面白いです。出力（試行ごとの反復回数）の最初の数は異なりますが、何度実行しても振動に収束します。ここ は、出力の2つの例である：

1st run   2nd run 
1 28278   1 13583 
2 7754   2 7308 
3 11308   3 22580 
4 5093   4 6307 ** oscillation starts 
5 4952   5 42060 
6 5017   6 10485 
7 10400   7 8525  
8 6307 **  8 31061 
9 42060   9 6307 ** 1st period 
10 10485   10 42060 
11 8525   11 10485 
12 31061   12 8525 
13 6307 **  13 31061 
14 42060   14 6307 ** 2nd period 
15 10485   15 42060 

は、今私は（より良いオプションは、C++ 11で<rand>ライブラリである）rand()が仕事に最適な機能ではないことを知っています。 しかし、どのようにの最初の乱数からこの正確な期間に収束しているのですか 6307 - 42060 - 10485 - 8525 - 31061？

観測：このプログラムでは、正確に2^31の乱数、つまりその期間、つまり乱数生成関数のサイクルが使用されます。 しかし、どのように？

Answer 1

rand()は深刻なものには使用しないでください。その品質はかなり悪いことがあります。

たとえば、私はそれを使ってシミュレーションを行い、正確な答えを知っています。 rand()では、シミュレーションは正確な答えとは若干異なる数に収束しました。私はより良い何かをrand()を置き換え、そして：

• シミュレーションでは、シミュレーションは厳密解に収束
• 3倍速くなります。

代わりにメルセンヌ・ツイスターを使用することをお勧めします。しかし、MTでもshortcomingsがあり、BigCrushテストに合格しません。

（xorshift128+）しかし、この単純な乱数発生器が通過すると、非常に高速：

uint64_t s[2]; // seed this 

uint64_t next(void) { 
    uint64_t s1 = s[0]; 
    const uint64_t s0 = s[1]; 
    const uint64_t result = s0 + s1; 
    s[0] = s0; 
    s1 ^= s1 << 23; // a 
    s[1] = s1^s0^(s1 >> 18)^(s0 >> 5); // b, c 
    return result; 
} 

http://xoroshiro.di.unimi.it/をチェックアウトし、彼らの最新発電機、xoroshiro128+