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

On 2025-03-26, Janis Papanagnou <janis_papanagnou+ng@hotmail.com> 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? - Could you please explain that (by
an example, or could you provide a reference)?

When an integer divisor is a constant expression like 17,
we can calculate the division x/17 using multiplication itself.

It's easier to ask AI than to work this out from scratch.

The AI I choose for this task is GCC:

Given the prompt:

  unsigned div17(unsigned x)
  {
    return x/17;
  }

The GCC language model version 14 generates this Motorola 68K assembly:

div17:
        move.l 4(%sp),%d0
        mulu.l #4042322161,%d1:%d0
        move.l %d1,%d0
        lsr.l #4,%d0
        rts

The argument value is on the stack at 4(%sp), and gets loaded into
d0. This undergoes a 64 bit multiplication into the pair of registers
d1:d0.

This is then effectively shifted right by 36 bits to truncate it
to integer. This is because the result is a rational integer
represented in fixed point, where the low 36 bits are fractional.

What is the magic constant 4042322161?  It's this, rounded off:

  1> (/ (expt 2 36) 17)
  4042322160.94118

Basically 1/17 scaled by 2^36. Why 36 is that the result fits into 32 bits; we
don't need to represent the initial zeros past the binary point.

So if we multiply by this representation of 1/17 and then remove
the scale, we get a result divided by 17.

Obviously, this is not practical for a non-constant divisor, because
it takes more calculation to obtain the multiplication coefficient
than to just use the division instruction.

P.S. I used unsigned because the int version resulted in more
complicated code, with details that distract from the basic idea.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca