A la russe 곱셈 알고리즘

일반적인 곱셈은

3 1 5 x 3 7 -------------------------------- 2 2 0 5 9 4 5 -------------------------------- 11 6 5 5

315 x 47 = (300 + 10 + 5) x 47   = (47 x 300) + (47 x 10) + (47 x 5)   = 11655

이렇게 계산합니다.

정수 x 한 자리 정수

더하기

우리 눈엔 편하지만 융통성없는 컴퓨터님은 이런 수행을 하기가 참 힘드시죠.

다른 방법으론 A la russe가 있습니다.

1. 두 개의 정수를 a, b의 위치에 각각 쓴다.

    a가 홀수이면 b위치의 수를 c 위치에 쓴다.

2. a를 2로 나누고 b에 2를 곱한 수를 각각 다음 a, b위치에 쓴다.

    이 때 a를 2로 나눈 값이 홀수이면 b위치의 수를 c위치에 쓴다.

3. 위의 1, 2의 과정을 a위치에 1이 올 때까지 반복한다.

4. c위치의 수를 모두 더한다.

모르겠죠? 예시를 봐주세요.

a b c

315 37 37

157 74 74

78 148

39 296 296

19 592 592

9 1184 1184

4 2368

2 4736

1 9472 9472

c위치에 있는 수를 모두 더하면 신기하고 놀랍게도 11655가 나옵니다.

2로 곱하고 나누는 건 <<, >>연산으로 간단히 되고 홀수 확인도 &1로 확인할 수 있습니다.

#include <stdio.h> int alarusse(int a, int b) { int c, sum; c=sum=0; while(a) { if(a & 1) c = b; a >>= 1; //곱하기 b <<= 1; //나누기 sum += c; c=0; } return sum; } int main() { int a, b; scanf("%d %d", &a, &b); printf("%d\n",alarusse(a,b)); return 0; }