알고리즘/러시아 농민 알고리즘(Russian peasant multiplication)

SangHoon Hwang·2020년 10월 6일

Russian peasant multiplication

2020-2 알고리즘

목록 보기

4/5

// 2020년 10월 6일 화요일 4번째 글
// 작성자: 황상훈

// lg(n) = log2(n)

러시아 농민 알고리즘이란 무엇인가?

Multiplication algorithm 중 한 가지.

2를 곱하고, 나누고, 더하면 모든 곱셈을 계산할 수 있는 곱셈 방법.

알고리즘의 내용은 다음과 같다.

1. 곱하고자 하는 두 수 A, B를 제일 첫 줄에 쓴다.(A가 작은 수)

2. A부터 시작하여 2로 나누고 나머지는 버린다.

3. 더 이상 나눌 것이 없을 때까지 2로 나누는 것을 반복하며, 결과를 아래에 차례대로 쓴다.

4. A를 나눈만큼 B를 곱한다. 마찬가지로 아래에 차례대로 쓴다.

5. A단에서 홀수가 있는 줄에 있는 B단의 숫자들을 모두 더하면, 그것이 곱셈의 결과가 된다.

예를 들어보자,

14 * 135를 계산해야 하는 경우라고 한다면, (작은 수를 A라고 한다)

A	B	(A가 홀수일 때 B의 값, 나중에 더한다)
14	135	null
7	270	270
3	540	540
1	1080	1080
null	null	270 + 540 + 1080 = 1890 (14 * 135 = 1890으로 결과가 같다)

러시아 농부 알고리즘은 이진법과도 관계가 있는데, 다음 예를 통해서 알아본다.

위에서 곱셈 계산에 이용한 14를 이진수로 표현하면

14 = (2^0 x 0) + (2^1 x 1) + (2^2 x 1) + (2^3 x 1) 이다.

여기에서, 곱셈의 분배법칙을 이용해서 각 항에 135를 곱하게 되면, 결과는 위에서 계산한 1890과 같다.

이것은 러시아 농부 알고리즘으로 계산하는 방법과 유사하다는 것을 알 수 있다.

러시아 농부 알고리즘은 프로그램으로도 간단하게 만들 수 있다.

다음은 C로 작성된 프로그램이다.
(곱하려는 두 수 n과 m이 0과 음수가 아니라는 가정하에 올바르게 동작할 수 있다)


#include <stdio.h>

int main(void) {
	int n = 14, m = 135;
    int sum = 0;
    
    while(n > 0) {
    	if((n % 2) == 1)
        	sum += m;
            
        n = n >>= 1;  // n을 2로 나눈다.
        m = m <<= 1;  // m을 2로 곱한다.
    }
    
    printf("%d \n", sum);
    
    return 0;
}

그렇다면, 이 알고리즘이 어떤 부분에서 의의를 가지는지 생각해보았다.

1. 일반적인 곱셈보다 연산 횟수가 적어 수행시간에서 이득이 있다.

일반적으로 초등학생 때 배운 곱셈은 Long multiplication 이라고 하는데, 알고리즘을 살펴보면 다음과 같다.


 multiply(a[1..p], b[1..q], base)                            // Operands containing rightmost digits at index 1
  product = [1..p+q]                                        // Allocate space for result
  for b_i = 1 to q                                          // for all digits in b
    carry = 0
    for a_i = 1 to p                                        // for all digits in a
      product[a_i + b_i - 1] += carry + a[a_i] * b[b_i]
      carry = product[a_i + b_i - 1] / base
      product[a_i + b_i - 1] = product[a_i + b_i - 1] mod base
    product[b_i + p] = carry                               // last digit comes from final carry
  return product

위의 의사코드(pseudocode)를 보면 알 수 있듯이, Long multiplication의 시간 복잡도는 Θ(n^2)이 된다.

반면에, 러시아 농부 알고리즘은 while 루프의 호출 횟수가 log2(n)이기 때문에 시간 복잡도는 Θ(lg(n))이 된다.

2. 러시아 농민 알고리즘을 조금 변형하면 지금 컴퓨터가 쓰는 곱셈 알고리즘이다.

이 부분은 아직 내가 이해하지 못했다.

관심이 있는 사람은 출처를 참고하거나, 직접 찾아보면 좋을 것이다.

// 출처