Russian Peasant Multiplication

The way most people learn to multiply large numbers looks something like this:

    86
  x 57
 ------
   602
+ 4300
 ------
  4902

If you know your multiplication facts, this "long multiplication" is quick and relatively simple. However, there are many other ways to multiply. One of these methods is often called the Russian peasant algorithm. You don't need multiplication facts to use the Russian peasant algorithm; you only need to double numbers, cut them in half, and add them up. Here are the rules:

• Write each number at the head of a column.
• Double the number in the first column, and halve the number in the second column.
     If the number in the second column is odd, divide it by two and drop the remainder.
• If the number in the second column is even, cross out that entire row.
• Keep doubling, halving, and crossing out until the number in the second column is 1.
• Add up the remaining numbers in the first column. The total is the product of your original numbers.

Let's multiply 57 by 86 as an example:

Write each number at the head of a column.

57

86

Double the number in the first column, and halve the number in the second column.

57	86
114	43

If the number in the second column is even, cross out that entire row.

57	86
114	43

Keep doubling, halving, and crossing out until the number in the second column is 1.

57	86
114	43
228	21
456	10
912	5
1824	2
3648	1

Add up the remaining numbers in the first column.

57	86
114	43
228	21
456	10
912	5
1824	2
+ 3648	1
4902

Real Russian peasants may have tracked their doublings with bowls of pebbles, instead of columns of numbers. (They probably weren't interested in problems as large as our example, though; four thousand pebbles would be hard to work with!) Russian peasants weren't the only ones to use this method of multiplication. The ancient Egyptians invented a similar process thousands of years earlier, and computers are still using related methods today.

출처: http://mathforum.org/dr.math/faq/faq.peasant.html#binary

Source Code

#include<stdio.h>
 
int sum = 0;
 
int RPM(int a, int b){
    printf("%d %d\n",a,b);
    
    if(b%2!=0)
        sum += a;
    
    if(b==1)
        return a,b;
    else{
        a *= 2;
        b /=2 ;
    }
    RPM(a,b);
    
    return sum;
}
 
int main() {
   int a = 0, b = 0;
   
   scanf("%d%d",&a, &b);
   printf("--%d--\n",RPM(a,b));
   return 0;
}