Multiply two Numbers Without Using * Operator
Lets have a fun question. Multiply two numbers without using the * operator.
Here’s the code in C/C++:
main(a,b,m)
{
while (~scanf("%d%d",&a,&b))
{
m=0;
while (a)
{
if (a&1)
m+=b;
a>>=1;
b<<=1;
}
printf("%d\n",m);
}
}
The above code is a implementation of an algorithm better known as the Ethiopian Multiplication or the Russian Peasant Multiplication.
Here’s the algorithm :
- Let the two numbers to be multiplied be a and b.
- If a is zero then break and print the result.
- If a is odd then add b to the result.
- Half a, Double b. Goto Step 2.
NJOY!
-fR0DDY
nice logic
.I hope that u will come up with some new posts too.
speed
April 8, 2010 at 12:53 PM
Hi gaurav…
. I enjoyed working around the codes tried an extended version of the code above.. can you suggest me which of the codes will take less resources…?
Nice coding
main() { int a,b; int m=0; while (~scanf("%d%d",&a,&b)) { m=0; while (a) { if (a&2) { if (a&1) m+=b+b+b;//remain 3 else m+=b+b;//remain 2 } else if(a&1)//remain 1 m+=b; a>>=2; b<<=2; //printf("%d,%d,%d\n",a,b,m); //to see intermediate values } printf("(%d)\n",m); } }As you can see that this algorithm can be extented to higher form in (multiple of 8,16,32,64..). which of the algorithm will be best suited for normal calculations??
Ritesh
September 27, 2010 at 12:33 AM
[...] this I like Categories: Code LikeBe the first to like this post. Comments (0) Trackbacks (0) Leave a [...]
multiply two numbers without using * operator « AfroCoder's
January 28, 2011 at 8:14 PM