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

Answer 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))))))

Answer 2

This is for a code obfuscation contest? I think you can do better. Use misleading variable names instead of meaningless ones, for starters.

Answer 3

Answer with no multiplication or division:

function RPM(int a, int b){
    int rtn;
    for(rtn=0;rtn+=(a&1)*b,a!=1;a>>=1,b<<=1);
    return rtn;
}

Answer 4

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.

Answer 5

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

Answer 6

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