hamster 177 Report post Posted September 10 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. Share this post Link to post Share on other sites

Tim Ansell 4 Report post Posted September 10 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 Share this post Link to post Share on other sites

Piasa 0 Report post Posted September 10 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. Share this post Link to post Share on other sites

hamster 177 Report post Posted September 10 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. Share this post Link to post Share on other sites

Tim Ansell 4 Report post Posted September 11 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. Share this post Link to post Share on other sites

jpeyron 202 Report post Posted September 11 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 1 hamster reacted to this Share this post Link to post Share on other sites