Dividing by 10....

[hamster]

Tonight I discovered that this is a fast way to divide by 10 

unsigned div10(unsigned x) {
#ifdef REF
      /* Implement 32-bit division using divide */
      return x/10;
#else
      return (x * 0xCCCCCCCDLLU)>>35;
#endif
}

Just wanted to post it here in case it becomes of use to somebody. A variant It could most likely be used with a DSP48 block to divide shorter (20 or 23 bit) binary numbers with much less resources and latency than a 10-bit binary divider.

[Tim Ansell]

Where did you find that? It is almost as good as this one -> https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

[Piasa]

You can use the same method to divide by other constant values as well.  It is just (2**32) * (1/n) or some desired power of two.  The precision is based on how large the dividend can be as this defines when the rounding error becomes off by one.

You can also do a similar trick in an FPGA for mod, at least for some cases.  If you look at the fractional bits, there can be patterns that allow a few of the fractional bits to be used with a lookup table for the value of mod.  This is based on the modulus and how large the argument can get.

[hamster]

8 hours ago, Tim Ansell said:

Where did you find that? It is almost as good as this one -> https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

Sort of pen-and-papered it.

0xCCCCCCCD is 0.8*2^32, so it is d = i * (4/5*2^32) / 2^32  which reduces to d = i/10

expecting that I would have to do a fixup to pick up rounding errors, but then found it wasn't needed.

It turns out that GCC does this optimization by default, but uses a 32-bit multiply that splits the result across two registers (EDX:EAX), but the above method doesn't touch EDX so leaves a register free, and can be a tad quicker.

[Tim Ansell]

A friend pointed me to http://www.hackersdelight.org/magic.htm 

Quote

On this page you can compute the magic number for division by a given divisor, and the multiplicative inverse modulo 2**32, of any number in the range –2**31 to 2**32 – 1.
Magic numbers are used to convert division by a constant into a short program that uses the most significant 32 bits of the 64-bit product of the dividend and the magic number. Multiplicative inverses are used to convert "exact division" by a constant into an ordinary multiplication modulo 2**32.

Examples of magic numbers are shown on page 189 of Hacker's Delight, and examples of multiplicative inverses are shown on page 197.

 

 

[jpeyron]

Hi @hamster,

Thank you for posting your fast way to divide by 10. I moved your post to a newly created thread for just this type of information.

cheers,

Jon