โปรแกรม C++ สร้างตัวเลขสุ่มด้วยวิธี Multiply with Carry (MWC)

วิธี Multiply-with-Carry (MWC)

วิธี Multiply-with-Carry เป็นรูปแบบหนึ่งของตัวสร้าง Add-with-Carry ที่ Marsaglia และ Zaman 提出 เมื่อปี 1991 ข้อดีหลักของวิธีนี้คือ ใช้คณิตศาสตร์จำนวนเต็มของคอมพิวเตอร์ที่เรียบง่าย และนำไปสู่การสร้างลำดับตัวเลขสุ่มที่รวดเร็วมาก มีช่วงเวลา (periods) ยาวมาก ตั้งแต่ประมาณ 2^60 ถึง 2^2000000

ใน MWC ฐาน (base) b ถูกเลือกให้เท่ากับขนาดคำของคอมพิวเตอร์ (computer word size) และตัวคูณ (multiplier) a และ lag r กำหนด modulus p = a*b^r - 1 ที่นี่ a ถูกเลือกทำให้ modulus เป็นจำนวนเฉพาะ และตัวคูณมีช่วงเวลายาว

อัลกอริทึม

เริ่มต้น
  ประกาศ maximum_sequence_elements, b, r, c[maximum_sequence_elements], x[maximum_sequence_elements]
  อ่านตัวแปร maximum_sequence_elements, b, r
  m = rand() mod b
  c[0] = rand() mod m
  x[0] = rand() mod b
  For I = 1 ถึง maximum_sequence_element
    x[i] = (m * x[i - r] + c[i - 1]) mod b
    c[i] = (m * x[i - r] + c[i - 1]) / b
  พิมพ์ลำดับ
สิ้นสุด

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

#include <iostream>
using namespace std;

int main(int argc, char **argv) {
    int max_Seq_Elements = 7;
    int b = 300;
    int m = rand() % b;
    int r = 1;
    int c[max_Seq_Elements];
    int x[max_Seq_Elements];
    c[0] = rand() % m;
    x[0] = rand() % b;
    cout << "The random number sequence is: " << x[0];
    for (int i = 1; i < max_Seq_Elements; i++) {
        x[i] = (m * x[i - r] + c[i - 1]) % b;
        c[i] = (m * x[i - r] + c[i - 1]) / b;
        cout << " " << x[i];
    }
    cout << "...";
}

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

The random number sequence is: 177 173 226 221 56 157 84...