Which is more computationally efficient: multiplication or 0 padding?

Question

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?

Answer 1

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.

Answer 2

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).