Thread: Division by ten with magic numbers

Hi everybody.

While I was experimenting a little with magic number to perform
a division with the method Malcom explained in another post ===> Look Here
and that I quote here for your convenience:

In case anyone wants more information on how I've performed divisions using multiply and shift. The theory is that instead of doing answer = x / y you are doing answer = ((x << n) / y) >> n (the shifts logically cancel out). Rewritting the shift as a multiply by a power of two answer = (x * 2^n / y) >> n and all I'm doing is pre-calculating 2^n / y. From there it's simply a matter of picking a large enough n whilst avoiding overflow, and making sure you round up.
Take this (num2*5243)>>19 it performs a divide by 100 for any number up to 10000...

To pick those magic numbers I first picked a power of two that was large enough that when divided by the divisor it was at least half as big as the number I want to support and that when multiplied by answer, doesn't exceed 2^32
2^19 = 524288
divide by divisor -> 524288 / 100 = 5242.88 -> 5243 (rounding up) (at least half as big as 10000 - check)
multiplied by quotient -> 5243 * 10000 = 52430000 (less than 2^32 - check)

I could instead have picked 2^20 giving (num2*10486)>>20
2^20 = 1048576
divide by divisor -> 1048576/ 100 = 10485.76 -> 10486 (rounding up) (at least half as big as 10000 - check)
multiplied by quotient -> 10486 * 10000 = 104860000 (less than 2^32 - check)

I was wondering about the use of C99 long long unsigned and the possibility to use
this data type to perform division by multiplication of bigger numbers than those we can
handle with 32 bit integers.

Anybody has some experience about this matter?

If we use long long integers or unsigned the following code to perform
a division by ten can handle bigger numbers providing a bigger magic number and
the relative shift?

Code:

      div = (num1 * 6554UL) >> 16;
      remain = num1 - div * ten;

The above code can handle division by multiplication of numbers not bigger than 99,999.

Any help would be very appreciated.

I think that code only worked up to around 16384 for the divisor, so I was using it for up to 9999. I'm pretty sure it doesn't work correctly for 99999.

The main difference between using a 64-bit data type and letting the compiler perform the same optimisation itself, is for an x86 program the assembly code can perform the multiplication one two 32-bit numbers to produce the 64-bit result. Whereas to get a 64-bit result from C or C++, you have to start with a 64-bit data type, so in effect it becomes a 64-bit x 64-bit multiplication, which isn't so easily handled by the 32-bit processor.

This is just one of those cases where the higher-level lanaguage doesn't allow you to specifiy things that map directly to the relevant assembly. Another example is performing a bit-rotate. Processors have an instruction for that, but to do it in C requires two shifts and an or.
It's one of those things that's really best left for assembly language coding, but you can do it in C if you make some compromise.