3

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);
5
  • I like optimal code so I'll give you an upvote, but you should have admitted in the above comments that your pre-edited post didn't have the initialization. Nov 4, 2008 at 1:59
  • @Lance yes,you are right,I will modify this
    – xxxxxxx
    Nov 4, 2008 at 2:02
  • My upvote because short onliner indentation MAY be poor. Though, it'd be very pleasant to read nice, indented code.
    – temoto
    Mar 6, 2009 at 18:22
  • spx looks like people hate you. im not sure why Dec 25, 2009 at 22:08
  • yes, people hate me, only hate all around. I don't know why, maybe you have an answer ? compact code produces hate, I cannot say it was didactical/instructive in any conceivable way. the intent obvious intent was vanity(burn in hell I will). this may be a possible explanation for the hate that you mention. What do you think ?
    – xxxxxxx
    Dec 31, 2009 at 14:33

10 Answers 10

56

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))))))
0
20

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.

7
  • yes,that was my first implementation :) then I remembered some tricks :)
    – xxxxxxx
    Nov 4, 2008 at 1:31
  • 3
    I hope I never have to write code with you, ever. I can't see why anyone would take something like the above and produce what you have, unless they were making a half-arsed attempt at an Obfuscated C contest entry. :|
    – Rob Howard
    Nov 4, 2008 at 1:41
  • 1
    I would think that bit shifting would be faster than division or multiplication, and I'm not sure if all compilers would do it that way. (Though they might, not sure here). Nov 4, 2008 at 1:58
  • 3
    bit shifting IS faster than multiplication or division BUT any decent compiler will optimise a multiplication by a constant into a set of bitshifts if at all possible. The only compiler I ran into that didn't is an IAR H8 compiler. I suspect that's not the target platform here. Nov 4, 2008 at 3:17
  • 7
    Vlad - I can read English too, but thatdoesn'tmeanIprefertoreaditlikethis. Mar 16, 2010 at 12:23
14

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

7

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);
1
  • yes,that is true my friend,fantastic ! thank you :) but the restriction b>0 has saved you here,were it not for that you would've been wrong.
    – xxxxxxx
    Nov 4, 2008 at 1:42
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 );
4

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

4

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.

1
  • p is to be initialized with 0 multiplication here works just for a>0,b>0 :) thanks for asking
    – xxxxxxx
    Nov 4, 2008 at 1:28
3

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

5
  • a,b are the numbers,after the for loop p will be their product. there,it's not hard to read.
    – xxxxxxx
    Nov 4, 2008 at 1:23
  • it is harder to read than it needs to be, and the person who wrote it is not the person to judge whether it is hard to read. What's wrong with adding a few linebreaks? Nov 4, 2008 at 1:24
  • adding linebreaks breaks compactness :)
    – xxxxxxx
    Nov 4, 2008 at 1:30
  • you mean "adding linebreaks breaks unreadability". Doesn't change the compiled size. Nov 4, 2008 at 1:32
  • 2
    Why don't you just write in assembly and stop screwing around with these play languages like C. You're obviously an outstanding programmer and you should probably go into teaching or consulting.
    – Tim
    Nov 4, 2008 at 1:53
3
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;
}
0

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;
}
1
  • 5
    err... (a&1)*b IS a multiplication. :)
    – vladr
    Mar 9, 2010 at 17:36

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.