개요
미드 스퀘어(Mid-Square, 제곱 중간값) 방법은 의사 난수(pseudorandom number)를 생성하는 고전적인 기법 중 하나입니다. 이 방법은 수학자이자 컴퓨터 과학의 선구자인 존 폰 노이만(John von Neumann)이 1949년 학회에서 발표하면서 널리 알려지게 되었습니다.
동작 원리
- 초기 시드(seed) 값을 하나 선택하고, 그 값을 제곱합니다.
- 제곱 결과에서 가운데 자릿수 일부를 추출하고, 추출된 숫자들이 만든 새로운 수를 다음 시드 값으로 사용합니다.
예시로 이해하기
- 시드 값으로 3456을 선택합니다. 제곱하면 11943936이 됩니다.
- 결과에서 가운데 4자리인 9439를 새로운 시드로 취합니다. 제곱하면 89094721이 됩니다.
- 다시 가운데 4자리인 0947을 새로운 시드로 취합니다.
- 이 과정을 반복하여 계속해서 난수열을 생성합니다.
알고리즘
1. 초기 시드 값을 선택한다 2. 시드 값의 제곱을 구한다 3. 이전 결과에서 n자리 숫자를 추출하여 시드를 갱신한다
미드 스퀘어 방법은 해싱(hashing)에도 활용됩니다. 키 값을 제곱한 뒤 중간 비트나 자릿수를 추출하는 방식으로, 키의 분포가 균등할 때 비교적 좋은 해시 성능을 보입니다. 아래 예제는 현재 시각을 기반으로 시드를 만들어 미드 스퀘어 방식으로 해시 값을 얻는 C++ 프로그램입니다.
C++ 구현 예제
#include <iostream>
#include <ctime>
using namespace std;
long long getTime(){
time_t t = time(NULL);
struct tm *tm = localtime(&t);
long long x = (tm->tm_hour) * 50000000 + (tm->tm_min) * 100000 + (tm->tm_sec) * 5000 +
(tm->tm_mday) * 50 + (tm->tm_year);
return x;
}
long getHash(){
long long key = getTime();
key = key * key;
key = key / 10000;
key = key % 100000000;
return key;
}
int main(){
cout << "Random number: " << getHash() << endl;
return 0;
}코드 설명
getTime(): 현재 시스템 시간(시, 분, 초, 날짜, 연도)을 조합해 고유한 시드 값을 생성합니다.getHash(): 시드 값을 제곱한 후, 하위 자릿수 일부(/ 10000)를 버리고 상위 범위(% 100000000)만 남겨 가운데 성격의 값을 추출합니다.main(): 최종 해시(난수) 값을 출력합니다.
실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.
Random number: 10088419
마무리
미드 스퀘어 방법은 구현이 매우 간단하지만, 특정 시드 값에서 짧은 주기로 수렴하거나 0으로 빠질 수 있다는 한계가 있습니다. 따라서 실무에서는 보안 목적보다는 교육용 예제나 간단한 해시 함수 설계에 적합합니다. 그럼에도 불구하고 의사 난수 생성과 해싱의 기본 개념을 이해하는 데 훌륭한 출발점이 되는 알고리즘입니다.