Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
1  
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++. –  Pål GD Jan 31 '13 at 11:56
    
If shifting is faster, your compiler (assuming some optimization is requested) does it on its own, or deserves to get replaced. –  vonbrand Jan 31 '13 at 16:55
2  
Looks like a possible case of premature optimisation to me. –  Raphael Feb 1 '13 at 10:45
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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