C++ fast division/mod by 10^x

Question

Hi All

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

ex:

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

or

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

If i am going to use bite 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 ?? Thank you

Answer 1

Not unless you're architecture supports Binary Coded Decimal, and even then only with lots of assembly messiness.

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

}

Answer 3

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 4

If the divisor is an explicit compile-time constant (i.e. if your x in 10^x is a compile-time constant), there's absolutely no point in using anything else than the language-provided / and % operators. If there a meaningful way to speed them up for explicit powers of 10, any self-respecting compler will know how to do that and will do that for you.

The only situiation when you might think about a "custom" implementation (aside from a dumb compiler) is the situation when x is a run-time value. In that case you'd need some kind of decimal-shift and decimal-and analogy. On a binary machine, a speedup is probably possible, but I doubt that you'll be able to achieve anything practically meaningful. (If the numbers were stored in binary-decimal format, then it would be easy, but in "normal" cases - no.)