러시아 농민 곱셈(Russian Peasant Multiplication)은 두 개의 큰 수를 빠르게 곱할 수 있는 고전적인 알고리즘입니다. 이 방법은 나눗셈과 곱셈 대신 비트 시프트 연산만을 사용하기 때문에 매우 효율적이며, 컴퓨터의 이진수 연산 특성과 잘 맞아떨어집니다.
알고리즘의 원리
이 알고리즘의 핵심 아이디어는 다음과 같습니다.
- 한쪽 숫자(n)를 계속 2배(왼쪽 시프트)하고,
- 다른 쪽 숫자(m)를 계속 절반으로 나누고(오른쪽 시프트),
- m이 홀수일 때마다 현재의 n 값을 결과에 더합니다.
m이 0이 되면 지금까지 누적된 결과값이 두 수의 곱이 됩니다.
알고리즘 의사 코드
Begin
Russianpeasant(num1, num2)
Int result = 0
while (num2 > 0)
if (num2 and 1)
result = result + num1
num1 = num1 left shift 1
num2 = num2 right shift 1
return result
End
C++ 예제 코드
#include <iostream>
using namespace std;
unsigned int russianPeasant(unsigned int n, unsigned int m) {
int result = 0;
while (m > 0) {
// m이 홀수이면 현재 n 값을 결과에 더함
if (m & 1)
result = result + n;
// n은 2배로, m은 절반으로
n = n << 1;
m = m >> 1;
}
return result;
}
int main() {
cout << russianPeasant(10, 20) << endl;
cout << russianPeasant(7, 6) << endl;
return 0;
}
실행 결과
200 42
동작 과정 살펴보기
예를 들어 russianPeasant(7, 6)의 동작을 단계별로 보면 다음과 같습니다.
- 1단계: m=6(짝수) → 결과는 그대로 0, n=14, m=3
- 2단계: m=3(홀수) → 결과에 14를 더해 14가 됨, n=28, m=1
- 3단계: m=1(홀수) → 결과에 28을 더해 42가 됨, n=56, m=0
- m이 0이므로 반복 종료, 최종 결과 42 반환
이처럼 러시아 농민 곱셈은 이진수 표현을 활용해 일반적인 곱셈 연산 없이도 두 수의 곱을 정확히 계산할 수 있는 우아한 알고리즘입니다.