본문 바로가기

(임시휴재) Fanta's Post

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로 확인할 수 있습니다.

'(임시휴재) Fanta's Post' 카테고리의 다른 글

Fanta's 포스팅연기  (1) 2009.04.25
제라의 공식으로 요일맞히는 프로그램  (2) 2009.04.19
이번주는 쉽니다.  (1) 2009.03.28
비트연산 활용  (0) 2009.03.21
최대공약수와 최소공배수  (0) 2009.03.14