Shift-Add vs Multiplication // Bit-Wise vs. Logical Operators

[ceatkin2]

I am trying to demonstrate to my class mates the run time difference in using
bit-wise and logical operators. I chose to do this by writing a simple (I thought) program
that reads 2 ints from the console, and multiplies them two separate times, one using
the logical multiply (a * b) and one using a shift-add algorithm. However, I am stumped in finding a way to use this method in all cases. Lets say that below is my program:

int x, y, logicalOp, bitwiseOp; 

logicalOp= x*y;


bitwiseOp= num << mult&num;

obviously, logicalOp and bitwiseOp should yield the same result.

The green text is what is giving me trouble. Can anybody offer some advice for a shift-add formula that works for small ints (<100)?

[N1GHTS]

Let me get this straight. So you want to prove to your peers that one technique is faster than the other, yet you are having trouble making the technique you are bragging about function correctly? Maybe its because the technique is flawed.

You see, multiplication in C using the multiplication operator '*' gets converted to something like this:

mov bx, 10
mul bx

Now the result of the multiplication by 10 is in bx. The clock cycles it takes to perform this is very little because the processor has logic gates executing a highly efficient shift-add method at nearly the speed of light.

Now, you try ANYTHING ELSE in C, and the compiler will absolutely add more lines of code to that. Like with that NUM << MULT & NUM, thats an initial MOV, an AND with a SHL and a final MOV., more work than MOV and MUL.

Even if you did this in assembly language it wouldn't be faster.

So I am frankly a little confused. Especially since NUM << MULT & NUM is not the shift-add method. To shift-add, you need to have a loop and perform ADD when the SHR has a carry.. well there's more to it than that but, one single line of code won't really cut it.

Here is more information on the shift-add multiplication method.

http://users.utcluj.ro/~baruch/book_ssce/SSCE-Shift-Mult.pdf

Now don't get me wrong, the shift-add multiplication method is very fast, faster than conventional math you do on paper, but keep in mind almost every processor in the modern world has this built in, and to code it in C can never be faster than MOSFET's doing the same thing.

[N1GHTS]

I just want to add that there are add-shift's that you can do with specific kinds of numbers which have less clock cycles than MUL (like mulitplying by 2 is faster just doing SHL) and on some processors, MUL is very slow compared to alternative ASM code, but do keep in mind that good C compilers are great at taking your math code and using the fastest method for your processor.

[ceatkin2]

I wouldn't say I was bragging about the idea as much as my professor gave my the assignment to write a program that demonstrates the run-time of each method. I agree it's trivial, but I would still like to know the logic. So, just to be clear, I'm looking for a way to multiply any two ints just using shifts and adds. It shouldn't be more than 1 or 2 lines of code.

[N1GHTS]

int mul(int x, int y) {
    int r = 0;
    for (;y!=0;y>>=1,x<<=1)
        if (y&1)
            r+=x;
    return r;
}

I would love to know if you or someone else could recode this so that it does less work.

[ceatkin2]

Nights, thanks for your help, I truly appreciate it. However,
I ran the code you supplied and it doesn't multiply the two numbers
to get the correct result. I've fiddled around with the numbers and it
seems that the answer it throws is half off from the actual answer.

[N1GHTS]

I replaced the variables a and b with a whole mess of random numbers and can't find a combination which will cause the terminal to show "failed". Tell me which numbers you are using and i'll plug it into my test program.

int main(int argc, char** argv) {
   int a = 2453,
       b = 354;

   int x = mul(a,b);
   int y = a * b;
   if (x!=y)
       printf("failed");
   else
       printf("success");

   return 0;
}

Output:

success