// 線形合同法と加算ラグ付フィボナッチ法を使った擬似乱数生成器
#include <iostream>
#include <deque>
#include <climits>
#include <iomanip>
#include <vector>
#include <cstdlib>
// 線形合同法
class LCGs {
int seed_; // 乱数の種
public:
LCGs() : seed_( 0 ) {}
LCGs( long seed ) : seed_( seed ) {}
void operator()( long seed ) { seed_ = seed; }
long operator()() {
seed_ = seed_ * 1103515245 + 12345;
return seed_ & LONG_MAX;
}
};
// 加算ラグ付フィボナッチ法
class ALFG {
typedef std::deque< long > Deq;
Deq seed_; // 乱数の種
void init_v( long seed = 0 ) {
// 最初の2個を線形合同法で決定した後、
// 32個(最初の2個を含む)のフィボナッチ数列を生成する
Deq temp(32);
LCGs lcg( seed );
temp[0] = lcg();
temp[1] = lcg();
for( int i = 2; i != 32; ++i ) {
temp[i] = temp[i - 1] + temp[i - 2];
}
seed_.swap( temp );
}
public:
ALFG() { init_v(); }
ALFG( long seed ) { init_v( seed ); }
void operator()( long seed ) { init_v( seed ); }
long operator()() {
// 乱数の種から6番目と31番目を使って次のフィボナッチ数を算出
long next = ( seed_[31] + seed_[6] ) & LONG_MAX;
seed_.pop_front();
seed_.push_back( next );
return next;
}
};
int main() {
using namespace std;
cout << setprecision( 20 );
int const max = 200;
// 線形合同法で乱数を max 個生成
cout << "線形合同法による乱数:\n";
LCGs lcgs( 1 );
for ( int i = 0; i != max; ++i ) {
cout << lcgs() << ", ";
}
cout << endl;
// 加算ラグ付フィボナッチ法で乱数を max 個生成
cout << "ラグ付フィボナッチ法による乱数:\n";
ALFG alfg( 1 );
for ( int i = 0; i != max; ++i ) {
cout << alfg() << ", ";
}
cout << endl;
// せっかくなので乱数の精度を検証
vector< double > v( 4, 0 );
alfg( 1 );
for ( int i = 0; i != max; ++i ) {
long n = alfg();
double d = double( n ) / LONG_MAX;
v[0] += d;
v[1] += d * d;
v[2] += d * d * d;
v[3] += d * d * d * d;
cout << n << ", ";
}
cout << endl;
int n = 1;
for ( auto iter = v.begin(); iter != v.end(); ++iter ) {
double d = *iter / max;
cout << "次数 " << n << " : ";
cout << "平均 " << d << " : ";
cout << "誤差 " << abs( d - 1.0 / ( n + 1 ) ) << "\n";
++n;
}
return 0;
}