Bộ sinh tuyến tính đồng dư (Linear Congruential Generator) là một ví dụ rất đơn giản của bộ sinh số ngẫu nhiên. Đây là một trong các thuật toán bộ sinh số giả ngẫu nhiên lâu đời và nổi tiếng nhất. Hàm được dùng trong phương pháp này:
Xn+1 = (a·Xn + C) mod m
trong đó X là dãy các giá trị giả ngẫu nhiên, và
m, 0 < m — "modulus" a, 0 < a < m — "multiplier" c, 0 < c < m — "increment" X0, 0 < x0 < m — "seed" hoặc "giá trị bắt đầu"
là các hằng số nguyên xác định bộ sinh.
Lợi ích của phương pháp này là với việc chọn tham số thích hợp, chu kỳ được biết trước và dài.
Thuật toán
Bắt đầu
Khai báo lớp mRND
Tạo hàm Seed(số) gán biến _seed = số
Tạo constructor mRND
Khai báo _seed(0), a(0), c(0), m(2147483648)
Tạo hàm rnd()
Trả về _seed = (a * _seed + c) mod m
Khai báo a, c, m, _seed
Kết thúc
Khai báo lớp con MS_RND kế thừa từ mRND
Tạo constructor đọc a, c
Tạo hàm rnd() trả về mRND::rnd() dịch phải 16
Khai báo lớp con BSD_RND kế thừa từ mRND
Tạo constructor đọc a, c
Tạo hàm rnd() trả về mRND::rnd()
For x = 0 đến 6: In MS_RAND
For x = 0 đến 6: In BSD_RAND
Kết thúc
Mã ví dụ
#include <iostream>
using namespace std;
class mRND {
public:
void seed(unsigned int s) {
_seed = s;
}
protected:
mRND() : _seed(0), a(0), c(0), m(2147483648) {}
int rnd() {
return (_seed = (a * _seed + c) % m);
}
int a, c;
unsigned int m, _seed;
};
class MS_RND : public mRND {
public:
MS_RND() {
a = 214013;
c = 2531011;
}
int rnd() {
return mRND::rnd() >> 16;
}
};
class BSD_RND : public mRND {
public:
BSD_RND() {
a = 1016404597;
c = 12345;
}
int rnd() {
return mRND::rnd();
}
};
int main(int argc, char* argv[]) {
BSD_RND bsd_rnd;
MS_RND ms_rnd;
cout << "MS RAND:" << endl << "-----------" << endl;
for (int x = 0; x < 6; x++)
cout << ms_rnd.rnd() << endl;
cout << endl << "BSD RAND:" << endl << "-------------" << endl;
for (int x = 0; x < 6; x++)
cout << bsd_rnd.rnd() << endl;
return 0;
}
Kết quả đầu ra
MS RAND: ------- 38 7719 21238 2437 8855 11797 BSD RAND: --------- 12345 1915290694 1005338679 629284700 741596485 1834373826