Russian Peasant Multiplication

Question

Here is my short implementation of Russian Peasant Multiplication. How can it be improved?

Restrictions : only works when a>0,b>0

for(p=0;p+=(a&1)*b,a!=1;a>>=1,b<<=1);

Solution 1

It can be improved by adding whitespace, proper indentation, and a proper function body:

int peasant_mult (int a, int b) {
  for (p = 0;
       p += (a & 1) * b, a != 1;
       a /= 2, b *= 2);
  return p;}

See? Now it's clear how the three parts of the for declaration are used. Remember, programs are written mainly for human eyes. Unreadable code is always bad code.

And now, for my personal amusement, a tail recursive version:

(defun peasant-mult (a b &optional (sum 0))
  "returns the product of a and b,
   achieved by peasant multiplication."
  (if (= a 1)
      (+ b sum)
      (peasant-mult (floor (/ a 2))
                    (* b 2)
                    (+ sum (* b (logand a 1))))))

Solution 2

I think it's terrible This is exactly the same code from the compiler's point of view, and (hopefully) a lot clearer

int sum = 0;
while(1)
{
    sum += (a & 1) * b;
    if(a == 1)
       break;

    a = a / 2;
    b = b * 2;
}

And now I've written it out, I understand it.

Solution 3

There is an really easy way to improve this:

p = a * b;

It has even the advantage that a or b could be less than 0.

If you look how it really works, you will see, that it is just the normal manual multiplication performed binary. You computer does it internaly this way (1), so the easiest way to use the russian peasant method is to use the builtin multiplication.

(1) Maybe it has a more sophasticated algorithm, but in principle you can say, it works with this algorithm

Solution 4

There is still a multiplication in the loop. If you wanted to reduce the cost of the multiplications, you could use this instead:

for(p=0;p+=(-(a&1))&b,a!=1;a>>=1,b<<=1);

Solution 5

I don't find it particularly terrible, obfuscated or unreadable, as others put it, and I don't understand all those downvotes. This said, here is how I would "improve" it:

// Russian Peasant Multiplication ( p <- a*b, only works when a>0, b>0 )
// See http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
for( p=0; p+=(a&1)*b, a!=1; a>>=1,b<<=1 );

View more solutions