Re: Fast division (was Re: Suggested method for returning a string from a C program?)

On 26/03/2025 14:47, Janis Papanagnou wrote:

On 26.03.2025 12:40, David Brown wrote:

>
[ substituting a division by multiplication (and some primitives) ]

>
Roughly speaking, when you want division of "y" by a fixed - i.e.,
constant value known at compile time - number "x", you can do it by
pre-calculating z = 2^n / x and then you implement "y / x" by "y * z /
2^n".  (There's also some stuff to handle correct rounding, especially
with signed types.)

 Thanks for the terse explanation; the formulas helped me to detect
that the constants in Waldek's assembler code are the pre-computed
reciprocals.
 First I thought that there's a trick to avoid division of non-const
expressions.
 

For non-constant divisors, it's a bit more difficult!  If you are going to use the same divisor several times, it can be worth computing the scaled reciprocal, so that you only have one hard operation.  I believe that hardware floating point units do that anyway for division.