C++로 곱하기-캐리(Multiply-with-Carry) 방식 난수 생성 프로그램 만들기

곱하기-캐리(Multiply-with-Carry) 방법이란?

곱하기-캐리(MWC) 방법은 Marsaglia와 Zaman이 1991년에 발표한 더하기-캐리(Add-with-Carry) 생성기의 변형입니다. 이 방법의 가장 큰 장점은 단순한 컴퓨터 정수 연산만으로 구현할 수 있다는 점과, 약 2⁶⁰에서 2^2000000에 이르는 엄청나게 긴 주기를 가진 난수 수열을 매우 빠른 속도로 생성할 수 있다는 점입니다.

MWC에서는 밑(base) b를 컴퓨터 워드(word) 크기와 같게 설정하며, 승수(multiplier) a와 지연(lag) r이 모듈러스 p = ab^r−1을 결정합니다. 이때 a는 모듈러스가 소수가 되고, 승수가 긴 주기를 갖도록 신중하게 선택됩니다.

알고리즘

시작
   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
   i = 1부터 maximum_sequence_elements까지 반복:
      x[i] = (m * x[i - r] + c[i - 1]) mod b
      c[i] = (m * x[i - r] + c[i - 1]) / b
      수열 출력
   반복 종료
끝.

예제 코드

다음 C++ 코드는 위 알고리즘을 실제로 구현한 것입니다. 밑 b는 300으로 설정되어 있으며, 초기값 x[0]과 캐리 값 c[0]은 rand() 함수를 통해 초기화됩니다. 이후 반복문에서 이전 값과 캐리 값을 이용해 새로운 난수와 캐리를 계산하고, 결과를 순서대로 출력합니다.

#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...

위 실행 결과에서 볼 수 있듯이, 프로그램은 총 7개의 난수로 구성된 수열을 생성합니다. 각 단계마다 새로운 값은 직전 값과 캐리 값을 기반으로 계산되므로, 동일한 초기 조건에서는 항상 같은 수열이 재현된다는 특징도 있습니다.