0

Is there an optimized way to multiply a*b without knowing the value of a and b and without using a loop where we do the ADD for a b times? Thank you

Develobeer
  • 425
  • 1
  • 8
  • 19
  • Why would you do that? What are you trying to achieve? – Yakov Galka Feb 01 '15 at 18:36
  • For example I must calculate a determinant of a matrix 2x2. I need of general solution so I must calculate for example a*e-b*d, but I need of optimized solution. I prefer to avoid the loop solution with ADD – Develobeer Feb 01 '15 at 18:40
  • No, not without knowing something about the values of `a` or `b`. (If `a` or `b` has a value of **0** or **1**, then we can't rule out the possibility that there's optimization for those particular cases. Otherwise, no, the `MUL` operation is already optimized. – spencer7593 Feb 01 '15 at 18:41
  • 5
    Use the MUL instruction. That's what it's for. – Raymond Chen Feb 01 '15 at 18:42
  • http://stackoverflow.com/questions/2069488/how-can-i-perform-multiplication-without-the-operator http://stackoverflow.com/questions/4456442/interview-multiplication-of-2-integers-using-bitwise-operators and since you didn't specify the architechture: http://stackoverflow.com/questions/21823625/arm-assembly-multiplying-without-mul-instruction http://stackoverflow.com/questions/9798813/how-do-i-implement-multiplication-and-division-in-mips-assembly-without-using-th – phuclv Feb 01 '15 at 18:45
  • 4
    Is there a way to multiply without mul instruction? Yes. Is there an optimized way? No – phuclv Feb 01 '15 at 18:47
  • @LưuVĩnhPhúc see tags. However edited title :) – Develobeer Feb 01 '15 at 18:58

1 Answers1

4

You can calculate a*b for n-bit numbers a and b by using n bit-tests, shifts and adds. But this is essentially what the MUL instructions does, in hardware, so you won't get anything faster than that.

Yakov Galka
  • 70,775
  • 16
  • 139
  • 220
  • 2
    To emphasise, using SHIFTs and ADDs will be significantly _slower_ than using MUL. Much slower. – H H Feb 01 '15 at 19:10