Guess the algorithm
January 23rd, 2010
Yesterday I found and programmed a nice little algorithm. I’m not going to tell you (yet) what it does and how its called, but I’ll just show the code:
private int function(int x, int y) {
int r = 0;
while(x!=0) {
if((x&1)==1) {
r+=y;
}
x>>>=1;
y<<=1;
}
return r;
}
So tell me, what does this do, and what is the algorithm called?
Edit:
And indeed (it was a simple one) the correct solution is multiplication, and to be specific, Ethiopian or Russian Multiplication.
I’ll probably do more, harder ones, in the future..!
3 Responses to “Guess the algorithm”
Leave a Reply
Multiply! :D
This is an excellent idea for a programming puzzle! The function multiplies x and y using the Shift and Add algorithm. There is another algorithm, which goes by a few different names, that reduces to the Shift and Add algorithm. You may know it as Binary Multiplication, Egyptian Multiplication, or (Russian) Peasant Multiplication.
We used to use this algorithm to multiply on 8 bit CPUs :-)