[알고리즘] a la russe 알고리즘 (곱셈 알고리즘)

 

 

[알고리즘] a la russe 알고리즘 (곱셈 알고리즘)

​

오늘은 곱셈 알고리즘인 a la russe 알고리즘에 대해서 이야기해보려 합니다.

 

먼저 우리가 일반적으로 사용하고 있는 곱셈 방식은 다음과 같습니다.

 

 

이렇게 간단하게 보이는 곱셈 방식도 사실 다음과 같은 수학적 관점에 의해서 설명할 수 있습니다.

 

 

분석해보면 먼저 자릿수 별로 구분짓고 곰셈을 행한뒤 자릿수에 맞게 더하면되는 방식입니다. 간단하죠?

 그럼 이제 a la russe 곱셈 알고리즘에 대해서 이야기해 볼 시간입니다. a la russe 곱셈 알고리즘은 다음과 같은 방식으로 이루어집니다. 한 번 따라서 해보시면 쉽게 이해가능하실겁니다.

 

1. 두 개의 정수를 첫번째, 두번째 위치에 기입한다.

2. 만약 첫번째 수가 홀수이면 두번째수를 세번째 위치에 또 기입하고 짝수라면 세번째 위치를 비워둔다.

​

3. 첫번째 수를 2로 나누고 나머지를 버린다. 그리고 두번째 수에 2를 곱한다.

4. 만약 첫번째 수가 홀수이면 두번째수를 세번째에 기입하고 짝수라면 세번째 위치를 비워둔다.

​

5. 다음과 같은 과정을 첫번째 위치의 수가 1이 될때까지 반복한다.

6. 최종적으로 세번째 위치에 있는 수를 모두 더하면 이 결과가 두 정수의 곱셈의 결과가 된다.

​

어떠신가요? 아무래도 글로 보니 이해가 힘드신가요? 아래의 예제를 한 번 따라가 봅시다.

​

​

 

고생많으셨습니다. 생각보다 어렵지 않죠? 오늘부터 알고리즘에 대한 자료를 하나하나 채워나가 보려합니다. 혹시 궁금하신점은 댓글달아주시면 답변드리겠습니다.