쉬운 농부 알고리즘

러시아 농부 알고리즘

 

러시아 농부 알고리즘 말로만 들었을 때는 이게 뭐지?? 할 겁니다 ㅋㅋ.

 

러시아어로 a la russe algorithm이라 불립니다.

 

두 정수의 곱셉을 하기 위한 또다른 알고리즘인데요.

 

러시아의 한 농부가 곱셈이 나타나기 전에 곱셈이 필요했답니다.

 

그래서 러시아 농부 곱셈 알고리즘이라고 불리는거죠.

 

이 알고리즘은 이집트 곱셈법과 많이 비슷한 형태를 취하고 있습니다.

 

방법에 대해 말해보자면

우선 두 정수를 첫 번째 열과 두 번째 열에 각각 씁니다.

 

첫 열에 숫자를 2로 나누고 몫을 두 번째 행의 첫 열에 쓰고

 

두 번째 열에있는 숫자를 2를 곱하여 만약 첫 열의 숫자가 홀수라면

 

세 번째 열에 2를 곱한 수를 써줍니다.

 

이렇게 첫 열 숫자가 1이 될 때까지 반복하여 세 번째 열에 있는 숫자를 다 더해줍니다.

 

이 값이 바로 두 정수를 곱한 결과입니다.

 

27 곱하기 82를 보죠.

 

	첫 열	두 번째 열	세 번째 열
첫 행	27 홀	82	82
두 번째 행	13 홀	164	164
세 번째 행	6 짝	328	x
네 번째 행	3 홀	656	656
다섯 번째 행	1 홀	1312	1312

 

빨간 색 숫자를 다 더해주면 2214로 27x82의 결과와 동일합니다.

 

제가 이 코드를 직접 짜봤습니다.

 

#include <stdio.h>

//이정찬 농부 알고리즘

int main(int argc,char **argv)
{
 //곱할 두 정수
 int a=27;
 int b=82;
 int first_result=a; // 첫 번째 열 담을 변수
 int second_result=b;// 두 번째 열 담을 변수
 int third_result=b;//세 번째 열 즉 더할 값들 담을 변수

 while(1)
 {
  first_result=first_result/2;//2로 나눈 몫을 담는다.
  second_result=second_result*2;//두 번째 열에 2를 곱한다.
  if(first_result%2==1)//첫 열이 홀수라면 세 번째 열 두 번째 열을 담는다.
  {
   third_result+=second_result;
    //세 번째열을 축적해서 더해준다.
  }
  if(first_result==1) //만약에 첫 열이 1이라면 종료
   break;

 }
 printf(" 농부 알고리즘 곱셈 결과:%d", third_result);
}

간단하지요?? 코드는 한번 분석 해보시기 바랍니다.