C++로 중간제곱법(Middle-Square Method) 난수 생성기 구현하기

중간제곱법(Middle-Square Method)이란?

중간제곱법은 난수를 생성하는 가장 단순한 방법 중 하나로, 존 폰 노이만(John von Neumann)이 1949년경 제안한 기법입니다. 동작 원리는 매우 간단합니다. 초기값(시드)을 제곱한 뒤 그 결과에서 가운데 자릿수들을 추출해 다음 난수로 삼고, 이 과정을 반복하여 난수열을 만들어냅니다.

다만 이 방법에는 분명한 한계가 있습니다. 어느 순간부터 같은 숫자를 반복해서 출력하거나, 이미 등장했던 수열로 되돌아가 무한히 순환할 수 있습니다. n자리 난수 생성기의 주기는 최대 8ⁿ을 넘지 못하며, 가운데 n자리가 모두 0이 되면 이후에는 영원히 0만 출력됩니다. 이런 0의 연속은 쉽게 감지할 수 있지만 너무 자주 발생하기 때문에, 중간제곱법은 실무보다는 학습용 예제로 더 적합합니다.

입출력 예시

입력 − 난수의 자릿수 입력: 4
출력 − 생성된 난수: 6383, 14846, 8067, 51524, .........

알고리즘

시작
   middleSquareNumber(number, digit)
   배열 a를 선언하고 next_number = 0으로 초기화한다.
   number를 제곱한 값을 변수 sqn에 대입한다.
   digit를 2로 나눈 값을 변수 t에 대입한다.
   sqn을 a[t]로 나눈 값을 sqn에 다시 저장한다.
   i = 0부터 digit까지 반복한다.
      next_number += (sqn mod a[t]) * a[i];
      sqn = sqn / 10;
   반복 종료
   next_number를 반환한다.
종료.

C++ 예제 코드

#include <iostream>
using namespace std;
int a[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000 };
int middleSquareNumber(int number, int digit) {
    int sqn = number * number, next_number = 0;
    int t = (digit / 2);
    sqn = sqn / a[t];
    for (int i = 0; i < digit; i++) {
        next_number += (sqn % (a[t])) * (a[i]);
        sqn = sqn / 10;
    }
    return next_number;
}
int main(int argc, char **argv) {
    cout << "원하는 난수의 자릿수를 입력하세요: ";
    int n;
    cin >> n;
    int start = 1;
    int end = 1;
    start = a[n - 1];
    end = a[n];
    int number = ((rand()) % (end - start)) + start;
    cout << "생성된 난수:\n" << number << ", ";
    for (int i = 1; i < n; i++) {
        number = middleSquareNumber(number, n);
        cout << number << ", ";
    }
    cout << ".........";
}

코드 핵심 설명

• 배열 a: 10의 거듭제곱(1, 10, 100, …)을 저장하여 원하는 자릿수만큼 값을 잘라내는 데 사용됩니다.
• t = digit / 2: 제곱 결과에서 가운데 자릿수의 시작 위치를 계산합니다.
• 반복문: sqn의 뒷자리부터 한 자리씩 추출하여 next_number를 조립한 뒤 반환합니다.

실행 결과

원하는 난수의 자릿수를 입력하세요: 4
생성된 난수:
6383, 14846, 8067, 51524, .........