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

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

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

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

Answer 6

p is not initialised.

What happens if a is zero?

What happens if a is negative?

Update: I see that you have updated the question to address the above problems. While your code now appears to work as stated (except for the overflow problem), it's still less readable than it should be.

Answer 7

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

Answer 8

I think it's incomplete, and very hard to read. What specific sort of feedback were you looking for?

Answer 9

int RussianPeasant(int a, int b)
{
    // sum = a * b
    int sum = 0;
    while (a != 0)
    {
        if ((a & 1) != 0)
            sum += b;
        b <<= 1;
        a >>= 1;
    }
    return sum;
}

Answer 10

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