Shankar Chakkere's Blog

Russian peasant method is one of the method I have used for multiplication of Integers over the years on processors that don't have explicit multiplication Instructions. Russian peasant method suits well because you just need instructions to double the number and halve the number, which is basically shift left and shift right respectively for a binary number. Almost all microprocessor will have these instructions and C language provides these operators << and >> respectively.

How it's done?

It is easy to explain the process with a diagram. Here it illustrates the multiplication of 5 x 4.
Step 1. If the multiplier is odd, add the multiplicand to the result. The red rows.
Step 2. Double the multiplicand.
Step 3. Halve the multiplier.
Step 4. Repeat step 1 to 3 till multiplier is zero.

You can switch the role of multiplicand and multiplier because of multiplication's commutative nature, doing so will reduce the number of iterations needed.

Here is the C code.

#include 

long multiply(int ml, int mp)
{
  long result =0;
   
  while( mp != 0)
  {
    if( mp & 01) /* if odd add ml to result */
    {
     result += ml;
     }
     ml <<= 1;
     mp >>= 1;
     
  }
  return result;
}

int main(void) 
{ 
  int x = 7;
  int y = 7;
  printf("%ld\n", multiply(x,y)); 
  return 0; 
} 

Labels: Embedded