우리는 이미  초등학교때 곱셈에 대해서 배웠을 것이다.

그럼 다음을 계산 하여 봐라.

 

 45 X 37

 

거의 100%의 확률로 다음과 같이 계산 할것이다.

 

     45

X   37

--------

    315

   135

---------

   1665

 

 

이것으 이미 초등학교때 배우는 곱셈 방식이다.

 

하지만 이것말고도 곱셈의 방식은 또 있다. 이른바 a la russe알고리즘이다.

 

일단 두개의 정수를 첫번째 위치 두번째 위치에 써둔다. 그리고 첫번째 위치는 계속 2로 나누고 두번째 위치에 있는 것은 계속 2로 곱한다.

 

첫번째 위치에  있는 것이 나눗셈할때 1이 남는경우 1은  신경쓰지않고  버린다.(2로 나누기에 나머지는 1과 0만 있을 뿐이다.)

 

첫번째 위치에 있는 것이 홀수일경우고 2번찌 위치에 있는것을  복사해서 따로 적어둔다. 그리고 첫번째 있는 수가 결국 1이 될때까지 계속 나눗셈을 해간다.

 

그리고 복사해서 적어둔것을 다 더하면 곰셈이 끝난다.  

 

/2          X2

45          37          37

 

22          74           .

 

11         148        148

 

5           296        296

 

2           592           .

 

1         1184        1184

 

-------------------------------

 

                   +  1665





나는 처음봄