Thread: Algorithm help

I have to write a program that multiplies two unsigned ints w/o using the * operator. Simple really, but there is a constraint on the algorthm. Although a simple way to go is

Code:

for (int i = 0; i < small_int; i++)
  {
   product = product + large_int;
   }

I cannot do that. The algorithm must run in time log2(min(x,y). I am slightly confused about how to go about this.

One way you could do this is store a mutliplication table in
a 2d array. Then just use the old grade school multiplication
method.

I don't have time to calculate it all out right now off the top of my head, but since it must be in log2 time then it would probably be something like keep doubling product floor(log2(min(x,y))) times and then finishing up with a straight loop. Like 8*10 would translate to 10+10+20+40 -- hope this helps.

I think this is what it wants take
x = 10011
y = 100111
Since x < y

Code:

100111
  10011

And you just do a normal binary multiplication. If x and
y are representive of the numbers then this algorithm
will do about lg(min(x, y)) additions. This
is since x is represented by about lg x bits.