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

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