C Program to multiply two numbers using Russian peasant method

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.

  1. Think of two numbers and write them at the head of the column.
  2. Multiply the first number by 2 and divide the second number by 2 (take integer division).
  3. Keep repeating step 2, until the second number is reduced to 1.
  4. Cross out the entire rows where the second number is even.
  5. 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

Product of 12 * 13 = 12 + 48 + 96 = 156

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

Expected Output:

1st run:

2nd run:

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:

 

Leave a Comment

%d bloggers like this: