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

On Wed, 26 Mar 2025 12:40:08 +0100
David Brown <david.brown@hesbynett.no> wrote:

On 26/03/2025 03:35, James Kuyper wrote:

On 3/25/25 21:04, Janis Papanagnou wrote: 

On 22.03.2025 15:07, Waldek Hebisch wrote: 

>
Actually, to do fast division of N-bit number by fixed N-bit
number one need 2N-bit multiplication. 

>
I just stumbled across your post and above sentence. Do you mean
*one* multiplication of 2N bit numbers? 

I think he meant "one needs 2N-bit multiplication". "one" is a
pronoun in this context, not a number. 

 
While that is probably correct, coincidentally it is also just /one/
multiplication.
 
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.)
 
So that is one use of multiplications that need longer bit-lengths,
beyond the size of the numbers you actually want to count (pennies or
whatever).
>

Strictly speaking, n-bit reciprocal is insufficient for arbitrary
n-bit [unsigned] integer division. For approximately 10% of divisors
one needs either n+1 bits of reciprocal or an adjustment step after
multiplication.
In cases like those compilers that implement division by constant via
multiplication by reciprocal are emulating multiplication by (n+1)-bit
reciprocal via multiplication by n-bit number followed by ether
subtraction or addition and shifts.