Chương trình C++ triển khai thuật toán sinh số ngẫu nhiên Park-Miller

Thuật toán sinh số ngẫu nhiên Park-Miller (Park-Miller Random Number Generation Algorithm) là một phương pháp khác để tạo số ngẫu nhiên.

Công thức chung của bộ sinh số ngẫu nhiên (RNG) loại này là: X_k+1 = g·X(k) mod n

Trong đó modulus n là một số nguyên tố hoặc lũy thừa của một số nguyên tố, hệ số nhân g là một phần tử có bậc nhân cao modulo n, và hạt giống X₀ nguyên tố cùng nhau với n.

Thuật toán

Bắt đầu
    Khai báo biến n, a, b, c và seed
    Đọc biến n, a, b, c và seed
    Uniform()
        Khai báo biến hi, lo, t
        hi = seed chia b
        lo = seed - b * hi
        t = a * lo - c * hi
        if (t > 0)
            seed = t;
        else
            seed = t + n;
        trả về seed;
    For i = 0 đến n
        Gọi hàm random
Kết thúc

Mã ví dụ

#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 << "Số ngẫu nhiên là:\n";
    for (int i = 0; i < 10; i++)
        cout << A[i] << endl;
}

Kết quả đầu ra

Số ngẫu nhiên là:
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