0
$\begingroup$

On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of simply padding the numbers with the required 0s. This padding will be nothing but some write operations (though random writes) in memory.

Which is more computationally efficient: multiplication or 0 padding?

$\endgroup$
  • 1
    $\begingroup$ Padding by 0's corresponds to multiplying by 2, not 10, so 10 zeroes should correspond to multiplying by 1024. They should however be pretty much the same if you are using, e.g., ints in C++. $\endgroup$ – Pål GD Jan 31 '13 at 11:56
  • $\begingroup$ If shifting is faster, your compiler (assuming some optimization is requested) does it on its own, or deserves to get replaced. $\endgroup$ – vonbrand Jan 31 '13 at 16:55
  • 2
    $\begingroup$ Looks like a possible case of premature optimisation to me. $\endgroup$ – Raphael Feb 1 '13 at 10:45
2
$\begingroup$

I'm assuming that your numbers are in binary. In this case, 0 padding is shift left: x << 3 is the same as x * 0x08, where 0x08 (hex) is 1000 (binary).

Shifting is much simpler to implement in hardware and is generally more efficient. You could check by writing a short C program.

Note that there is one significant difference between shift left and multiplication. The former does not signal if there is an overflow error, whereas the latter will.

$\endgroup$
2
$\begingroup$

If 1000 and 10000 are constants, then any decent compiler will figure out the most efficient way to do the multiplication by itself. This is platform dependent.

Any memory operation is most likely much more costly than multiplication (by orders of magnitude if the data is not in cache).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.