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