어 라 루스 (A La Russe)

1. 알고리즘 개요

우리가 일반적으로 두 자리 수의 정수를 곱할때, 초등학교에서 배운 것과 동일한 방법으로 계산하려면 아래처럼 써서 계산할 수 있다. 컴퓨터에서 이 것을 어떻게 구현할까?

 

[그림] 두자리 정수 곱셈

 

먼저  $22 \times 11$을  $22 \times (10 + 1)$로 쪼갠다. 그 뒤에 $22 \times 1$와 $22 \times 10$을 각각 구한 뒤 더하면 위와 같은 연산이 된다. 이러한 방식의 연산을 컴퓨터에서 구현하려면, 1의 자리 수 연산의 곱을 먼저 수행 한 뒤, 그 값을 저장해두었다가 10의 자리수 연산을 수행하여 더해야 하는데, 이러한 방식이 컴퓨터에서 구현하기 편리한 방식은 아니다. (이미 만들어진 C, Java 등의 언어에서는 그냥 곱하기 연산을 수행하면 되지만, 그 보다 아랫단계에서 우리가 프로세서를 구현한다고 가정해보자.) 때문에, 다음과 같은 알고리즘을 사용하면 컴퓨터에서도 편하게 자리 넘김값을 저장할 필요 없이 두자리 수 곱셈을 구현할 수 있다. 

 

---

A La Russe

 

(1) 먼저 세 칸을 만들고 두 수를 1번 째, 2번째 칸에 적는다.

이 때, 1번째 수가 홀수이면 2번째 칸의 값을 3번째 칸에 옮겨 적는다.

 

(2)  1번 째 칸에 있는 값을 2로 나누고, 2번 째 칸에 있는 값에 2를 곱한다.

이 때, 1번째 수가 홀수이면 2번째 칸의 값을 3번째 칸에 옮겨적는다.

이 것을 1번 째 칸에 있는 값이 0이 될 때 까지 반복한다.

 

(3) 3번째 칸에 적혀진 모든 값을 더하여 출력한다.

 

---

[그림] A La Russe를 이용한 곱셈

 

이 알고리즘을 이용하여 $45 \times 37$을 계산하면 위와 같이 계산된다. 이 계산과정이 왜 성립되는지 조금 더 자세히 알아보자. 이 알고리즘은 "2 x 2와 1 x 4는 동일하다"라는 원리를 이용하여 곱셈을 수행한다. 먼저 $45 \times 37$에 저러한 원리를 적용하려고 하는데 45가 홀수이기 때문에 1을 버리고 $44 \times 37 +37$을 수행한다. 때문에 맨 처음에 37을 3 번째 칸으로 빼 놓는 것이다. 그리고 44 x 37을 수행하는데 이는 22 x 74와 동일하다. 이후에 $22 \times 74$를 $11 \times 148$로 바꾼다. 그런데 11은 홀수이기 때문에 148을 하나 빼놓고 $10 \times 148$를 계산한다. 그 후에 $10 \times 148$을 $5 \times 296$으로 바꾼다. 5는 홀수이기 때문에 296을 빼놓고, $4 \times 296$으로 바꾼다. 이러한 방식으로 끝까지 계산하면 결국 $1 \times 1184$까지 나오고, 1은 홀수이기 때문에 3번 째 칸으로 옮기고 알고리즘을 종료한다. 

 

2. 소스 코드 : 

#include<cstdio>


int alarusse(int first, int second) {
    int third = 0; 
    // 더한 값을 기록할 변수 (세번째 칸)

    while (first > 0) { 
    // 만약 첫번째 칸의 숫자가 0보다 크다면 반복
    
        if (first % 2 == 1) { 
        // 첫번째 칸의 숫자가 홀수라면
        
            third += second;
            // 세번째 칸에 수를 더함
        }
        first = first >> 1; // 2로 나누기
        second = second << 1; // 2를 곱하기
    }
    // 첫번째 숫자가 1을 지나 
    // 0까지 떨어지면 알고리즘 종료

    return third;
}


int main() {
    int result = alarusse(45, 37);
    printf("%d", result); // 출력 : 1665

    return 0;
}

 

gusdnd852/TIL

전체 소스코드는 Github에서 확인하실 수 있습니다.

 

3. Reference :

 

'a la russe' 알고리즘(곱하기 알고리즘)