OverIQ.com

  1. Home
  2. C Programming Examples
  3. C Program to multiply two numbers using Russian peasant method

C Program to multiply two numbers using Russian peasant method

Last updated on September 23, 2020

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 the 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

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;
}

Try it now

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 Programming Examples

Recent Posts