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

On 26.03.2025 14:44, Waldek Hebisch wrote:

James Kuyper <jameskuyper@alumni.caltech.edu> 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.

 
Yes, of course "one" in my text above is a pronoun.  I do not know
how Janis guessed one multiplication, but it is correct guess.

The "one" was clear ("one need", "you need", "we need", etc.).

What was unclear was whether there's indeed only one multiplication
necessary. The "2N-bit multiplication" would also have been clear
from its writing; meaning "[one] multiplication of 2N bit entities".

But I couldn't imagine that a _general_ [non-const] division a/b
could be done with only one multiplication. That's were I speculated
whether you may have meant, say, "two N-bit multiplications" or some
such. - That's why I was asking for confirmation. - Later I saw that
you meant just a special case division a/c (with a _constant_ c),
which of course can be pre-computed.

Janis

[...]