C++ fast division/mod by 10^x

Question

In my program I use a lot of integer division by 10^x and integer mod function of power 10.

For example:

unsigned __int64 a = 12345; a = a / 100; .... 

or:

unsigned __int64 a = 12345; a = a % 1000; .... 

If I am going to use the right bit shift >>, then I will get mode of 2^x, which is not what I want.

Is there any way I can speed up my program in integer division and mod functions?

Answer 1

Short Answer: NO

Long Answer: NO.

Explanation:
The compiler is already optimizing statements like this for you.
If there is a technique for implementing this quicker than an integer division then the compiler already knows about it and will apply it (assuming you turn on optimizations).

If you provide the appropriate architecture flags as well then the compiler may even know about specific fast architecture specific assembles that will provide a nice trick for doing the operation otherwise it will apply the best trick for the generic architecture it was compiled for.

In short the compiler will beat the human 99.9999999% of the time in any optimization trick (try it remember to add the optimization flag and architecture flags). So the best you can normally do is equal the compiler.

If by some miracle you discover a method that has not already been found by the Assembly boffins that work closely with the backend compiler team. Then please let them know and the next version of the popular compilers will be updated with the 'unknown (google)' division by 10 optimization trick.

Answer 2

From http://www.hackersdelight.org/divcMore.pdf

unsigned divu10(unsigned n) { unsigned q, r; q = (n >> 1) + (n >> 2); q = q + (q >> 4); q = q + (q >> 8); q = q + (q >> 16); q = q >> 3; r = n - q*10; return q + ((r + 6) >> 4);  }