2017-07-02 33 views
-1

我做,我需要需要生成與N/2 0和其他1S最初N個元素的數組的問題的數值模擬。在每次迭代中,數組都被混洗,並且從前一次迭代中隨機選擇下一個數組元素,直到只剩下0或1。我記錄了T次試驗中的迭代次數。爲了生成隨機整數,我使用了使用rand()的丟棄模數方法(從here得到了這個想法)。蘭特():怪異的行爲

#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); 
    } 
} 

輸出非常有趣。輸出中的前幾個數字(每次試驗的迭代次數)不同,但是無論我運行多少次,它都會收斂到一個振盪。 下面是輸出的兩個例子:

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 

現在我知道rand()不是這個職位的最佳功能(更好的選擇是在C++ 11 <rand>庫)。 但它是如何從任何初始隨機數匯聚成了這個確切的時期 6307 - 42060 - 10485 - 8525 - 31061

觀察:程序在該期間即隨機數生成函數的循環使用恰好2^31隨機數。 但是如何?

+2

http://en.cppreference.com/w/cpp/numeric/random/rand – juanchopanza

+0

在C++中更好的選擇是使用random_device而不是 http://en.cppreference.com/w/cpp/numeric/random/random_device – 21koizyd

+0

[»質量沒有保證產生的隨機序列。在過去,rand()的一些實現在產生的序列的隨機性,分佈和週期方面有嚴重的缺陷。«](http://en.cppreference.com/w/cpp/numeric/random/rand)使用梅森扭轉者。如果您需要隨機數字進行加密,請使用OpenSSL(或LibreSSL)。 –

回答

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+