# C Program to multiply two numbers using Russian peasant method

Last updated on July 27, 2020

[no_toc]

## What is Russian peasant method? #

Russian peasant method allows us to find the multiplication of two numbers without using multiplication tables. In this method, we divide the numbers, half them and then add them up. Here are the steps to find multiplication using Russian peasant method.

- Think of two numbers and write them at the head of the column.
- Multiply the first number by 2 and divide the second number by 2 (take integer division).
- Keep repeating step 2, until the second number is reduced to 1.
- Cross out the entire rows where the second number is even.
- Take the sum of the remaining numbers in the first column. This sum is equal to the product of two original numbers.

Let's take an example: Example 1: Multiply 12 * 13 using Russian peasant method

Step 1: Write numbers at the head of the column:

col1 | col2 |
---|---|

12 | 13 |

Step 2: Multiply the first number by 2 and divide the second number by 2 (take integer division)

col1 | col2 |
---|---|

12 | 13 |

24 | 6 |

Step 3: Keep repeating step 2, until the second number is reduced to 1.

col1 | col2 |
---|---|

12 | 13 |

24 | 6 |

48 | 3 |

96 | 1 |

Step 4: Cross out the entire rows where the second number is even.

col1 | col2 |
---|---|

12 | 13 |

24 | 6 |

48 | 3 |

96 | 1 |

Step 5: Take the sum of the remaining numbers in the first column.

col1 | col2 |
---|---|

12 | 13 |

24 | 6 |

48 | 3 |

96 | 1 |

The product of 12 * 13 = 12 + 48 + 96 = 156.

The following is a C program to multiply two numbers using Russian peasant method:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | ```
/*************************************************************
Program to multiply two numbers using Russian peasant method
*************************************************************/
#include <stdio.h>
int main()
{
int a, b, result = 0, m, n;
printf("Enter two numbers: ");
scanf("%d %d", &a, &b);
m = a;
n = b;
while(n > 0)
{
if(n % 2 != 0)
{
result += m;
}
m *= 2; // double the first number
n /= 2; // half the second number
}
printf("%d * %d = %d", a, b, result);
return 0;
}
``` |

**Expected Output:** 1st run:

1 2 | ```
Enter two numbers: 12 13
12 * 13 = 156
``` |

2nd run:

1 2 | ```
Enter two numbers: 10 96
10 * 96 = 960
``` |

## How it works #

The following table demonstrates what happens at each iteration of the while loop, assuiming (`a = 12`

, `b = 13`

):

Iteration | `if condition` |
`result` |
`m` |
`n` |
---|---|---|---|---|

After 1st iteration | `13%2!=0=>1` |
`result=0+12=12` |
`m=12*2=24` |
`n=13/2=6` |

After 2nd iteration | `6%2!=0=>0` (cross the row) |
`result=12` |
`m=24*2=48` |
`n=6/2=3` |

After 3rd iteration | `3%2!=0=>1` |
`result=12+48=60` |
`m=48*2=96` |
`n=3/2=1` |

After 4th iteration | `1%2!=0=>1` |
`result=60+96=156` |
`m=96*2=192` |
`n=1/2=0` |

**Recommended Reading:**

- C Program to find Armstrong numbers
- C Program to find Prime Numbers
- C Program to convert the temperature in Fahrenheit to Celsius
- C Program to find the roots of a Quadratic equation
- C Program to print Triad Numbers

Load Comments