• State
  • Locked Locked
  • Replies 5 replies
  • Subscribers 81 subscribers
  • Views 453 views
  • Users 0 members are here
Support feedback
Options
Options
Related

This thread has been locked.

If you have a related question, please click the "Ask a related question" button in the top right corner. The newly created question will be automatically linked to this question.

How about Multiplication by this method

Deepak Bansal
Expert 2395 points

1. I had to multiply two integer variable.

e.g x=900;

x= x* 72;                                  // It took larger time to multiply.

2. Then I thought to multiply it by using shift operator. And I found binary equivalent of 72 i.e 1001000. & I did multiply by:

x = (x<<6) + (x<<3);                      // in above binary of 72, bit 3 & bit 6 are 1 rest are 0.

And I got the same result & in much lesser time.

3. Now this can be implemented to any number as there binary number can be found  & I think is a much better approach to multiply.

4. Is there any pitfall in this method or any other better method to multiply.

  • 0
    Expert 2855 points

    Dear Bansal,

    The time required to perform the operation will change from a minimum value, obtained when x = 0x00, to the maximum value observed when x = 0xff. You should first evaluate the worst situation, before you could conclude something.

    Best regards,

    AES

  • 0
    Guru 227245 points

    You're right, shifting is faster than multiplication. However, your method only works for a factor that is known at compiler time. Also, execution time and code size time extends with the number of '1' bits the factor has.

    Personally, I use an explicit shift whenever I have a factor of the power of two. But only then.

    On many MSPs, there is a hardware multiplier which is almost as fast as a shift - and faster than shifting when your factor has more than 3 bits set.

    But your observation is a good example of how to speed up code by optimizing a formula.

  • 0
    Guru 58965 points

    Deepak Bansal said:
    4... Is there any pitfall in this method or any other better method to multiply....

    A) This method is applicable only when one of the operants is a constant

    B) That constant must be known at compilation time.

    Aside from the above, it is not fashionable to do things like this. You should use "advanced technology", such as wider bus, faster CPU, more memory, more hardware, floating point, etc.

    If you are interested in ancient methods, try Horner’s method, which uses Shift, Add, as well as Subtract.

  • 0
    Guru 99715 points

    Some compilers do this as part of constant folding. The advantage is that the compiler re-writes the code if you change the constant. It also might not do it if it (the implementors) concluded that it wasn't cheaper than a multiply -- *3 or *255 e.g. do better than some others.

    Same rules though -- compile-time constants only.

  • 0
    Guru 58965 points

    Qin Jiushao, of the 13th century, wrote a book full of computational tricks. Unfortuenatly, he wrote it in C. (; Capital C -- his TTY-33 could not type in lowercase ;) One of his tricks is widely credited to William George Horner (1786 - 1837).

    When the binary presentation of multiplier has lots of consecutive 0’s or 1’s. You may save some computation if you know how to shift, add, and subtract. For example:

    255 = 11111111B = 256 – 1

    121 = 01111001B = 128 - 8 + 1

    72 = 01001000B = 64 +8

**Attention** This is a public forum