Russian peasant multiplication

Question

Here is my short implementation of Russian peasant multiplication . How can this be improved?

Limitations: 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 a space, the correct indentation, and the correct function body:

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

Cm? Now it turns out how the three parts of the for declaration are used. Remember that programs are written primarily for the human eye. Unreadable code is always bad code.

And now, for my personal entertainment, the tail recursive version:

 (defun peasant-mult (ab & 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 this is terrible. This is exactly the same code from the point of view of the compiler and (I hope) is much more understandable.

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

And now I wrote it, I understand it.

Answer 3

There is a very simple way to improve this:

 p = a * b; 

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

If you look at how this works, you will see that this is just ordinary binary manual multiplication. You use a computer in this way (1), so the easiest way to use the Russian peasant method is to use built-in multiplication.

(1) It may have a more complex algorithm, but in principle you can say that it works with this algorithm

Answer 4

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

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

Answer 5

I do not consider it particularly scary, confusing or unreadable, as others have expressed, and I do not understand all of these downvotes. This indicates how I will "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 not initialized.

What happens if a is zero?

What happens if a negative?

Update: I see that you updated the question to solve the above problems. Although your code now works as directed (with the exception of an overflow problem), it is even less readable than it should be.

Answer 7

Is it for obfuscating code? I think you can do better. Use misleading variable names instead of meaningless ones, for starters.

Answer 8

I think it is incomplete and very difficult to read. What specific feedback were you looking for?

Answer 9

So many downvotes. I do not see any harm that he caused by posting this!

PS For "learning" [games around], it is normal to make such a code. But professionally, I would not expect you to code like this!

Answer 10

 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 11

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