โปรแกรม C++ อัลกอริทึมสร้างตัวเลขสุ่ม Park-Miller

อัลกอริทึมสร้างตัวเลขสุ่ม Park-Miller

อัลกอริทึมสร้างตัวเลขสุ่ม Park-Miller เป็นอีกวิธีหนึ่งในการสร้างตัวเลขสุ่ม

สูตรทั่วไปของตัวสร้างตัวเลขสุ่ม (RNG) ประเภทนี้คือ: X_{k+1} = g X(k) mod n

โดยที่ modulus n เป็นจำนวนเฉพาะหรือกำลังของจำนวนเฉพาะ ตัวคูณ g เป็นสมาชิกที่มีออเดอร์การคูณสูง modulo n และ seed X0 เป็น coprime กับ n

อัลกอริทึม

เริ่มต้น
  ประกาศตัวแปร n, a, b, c และ seed
  อ่านตัวแปร n, a, b, c และ seed
  Uniform()
  ประกาศตัวแปร hi, lo, t
  hi = seed หาร b
  lo = seed - b * hi
  t = a * lo - c * hi
  if (t > 0)
    seed = t
  else
    seed = t + n
  return seed
  Done
  For i = 0 ถึง n
    เรียกฟังก์ชัน random
  Done
สิ้นสุด

โค้ดตัวอย่าง

#include <iostream>
using namespace std;

const long n = 2145678965L;
const long a = 763214L;
const long b = 88844L;
const long c = 7766L;
static long seed = 12345678L;

double uniform() {
    long hi = seed / b;
    long lo = seed - b * hi;
    long t = a * lo - c * hi;
    if (t > 0)
        seed = t;
    else
        seed = t + n;
    return seed;
}

int main(int argc, char **argv) {
    double A[10];
    for (int i = 0; i < 10; i++)
        A[i] = uniform();
    cout << "Random numbers are:\n";
    for (int i = 0; i < 10; i++)
        cout << A[i] << endl;
}

ผลลัพธ์ตัวอย่าง

Random numbers are:
6.50293e+10
4.27187e+10
2.1539e+10
4.62058e+10
1.70792e+10
8.24569e+09
5.93381e+10
3.63839e+10
4.81931e+10
8.91007e+09