ตัวสร้างตัวเลขสุ่มแบบ Linear Congruential Generator
ตัวสร้างแบบ Linear Congruential Generator เป็นตัวอย่างที่เรียบง่ายมากของตัวสร้างตัวเลขสุ่ม เป็นหนึ่งในอัลกอริทึม pseudorandom number generator ที่เก่าและรู้จักมากที่สุด ฟังก์ชันที่ใช้ในวิธีนี้คือ
X_{n+1} = (aX_n + C) mod m
โดยที่ X คือลำดับของค่า pseudorandom และ
m, 0 < m — "modulus" a, 0 < a < m — "multiplier" c, 0 < c < m — "increment" X₀, 0 < x₀ < m — "seed" หรือ "start value" เป็นค่าคงที่จำนวนเต็มที่ระบุตัวสร้าง
ประโยชน์ของวิธีนี้คือ ด้วยการเลือกพารามิเตอร์ที่เหมาะสม ช่วงเวลา (period) จะทราบและยาว
อัลกอริทึม
เริ่มต้น ประกาศคลาส mRND สร้างฟังก์ชัน Seed(number) กำหนดตัวแปร _seed = number สร้าง constructor mRND ประกาศ _seed(0), a(0), c(0), m(2147483648) สร้างฟังก์ชัน rnd() คืนค่า _seed = (a * _seed + c) mod m ประกาศ a, c, m, _seed Done ประกาศคลาสย่อย MS_RND 繼承จาก mRND สร้าง constructor อ่านตัวแปร a, c สร้างฟังก์ชัน rnd() คืนค่า mRND::rnd() ขวา 16 ประกาศคลาสย่อย BSD_RND 繼承จาก mRND สร้าง constructor อ่านตัวแปร a, c สร้างฟังก์ชัน rnd() คืนค่า mRND::rnd() For x = 0 ถึง 6 พิมพ์ MS_RAND For x = 0 ถึง 6 พิมพ์ BSD_RAND สิ้นสุด
โค้ดตัวอย่าง
#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;
}
ผลลัพธ์ตัวอย่าง
MS RAND: ------- 38 7719 21238 2437 8855 11797 BSD RAND: --------- 12345 1915290694 1005338679 629284700 741596485 1834373826
