Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Kaz Kylheku <643-408-1753@kylheku.com>
Newsgroups: comp.lang.c
Subject: Re: Fast division (was Re: Suggested method for returning a string
 from a C program?)
Date: Wed, 26 Mar 2025 18:49:12 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 63
Message-ID: <20250326113353.769@kylheku.com>
References: <vrd77d$3nvtf$2@dont-email.me> <868qp1ra5f.fsf@linuxsc.com>
 <vrdhok$47cb$2@dont-email.me> <20250319115550.0000676f@yahoo.com>
 <vreuj1$1asii$4@dont-email.me> <vreve4$19klp$2@dont-email.me>
 <20250319201903.00005452@yahoo.com> <86r02roqdq.fsf@linuxsc.com>
 <vrh1br$35029$2@dont-email.me> <LRUCP.2$541.0@fx47.iad>
 <vrh71t$3be42$1@dont-email.me> <vrk8vm$2f4gc$1@paganini.bofh.team>
 <20250321113316.506@kylheku.com> <vrl6hp$2qg20$1@dont-email.me>
 <20250321210228.508@kylheku.com> <vrmg7d$2nif7$2@paganini.bofh.team>
 <vrvjr9$i7gg$1@dont-email.me>
Injection-Date: Wed, 26 Mar 2025 19:49:12 +0100 (CET)
Injection-Info: dont-email.me; posting-host="59e26a12df5d8320043f4e2c1712d31f";
	logging-data="2477845"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX198GosyWQsUwd7nRp1vmFLnkym9PzuRNns="
User-Agent: slrn/pre1.0.4-9 (Linux)
Cancel-Lock: sha1:Bc4Ipm/Kx+KapBSiQIDemJpU5zo=

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