Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: David Brown <david.brown@hesbynett.no>
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 17:55:13 +0100
Organization: A noiseless patient Spider
Lines: 25
Message-ID: <vs1bhh$24nub$6@dont-email.me>
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> <vrvp60$m53l$1@dont-email.me>
 <vs0p2o$1look$1@dont-email.me> <vs10go$1sing$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Wed, 26 Mar 2025 17:55:13 +0100 (CET)
Injection-Info: dont-email.me; posting-host="9e00a15ae379d2cae7edd65ac25a9709";
	logging-data="2252747"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+9mYe6eUYoHLgfe1w041xhosnTM5QnPLM="
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.11.0
Cancel-Lock: sha1:KtXLpyc7EauP4LWKzn2vyU2MQ+I=
Content-Language: en-GB
In-Reply-To: <vs10go$1sing$1@dont-email.me>

On 26/03/2025 14:47, Janis Papanagnou wrote:
> On 26.03.2025 12:40, David Brown wrote:
>>>>
>>>> [ substituting a division by multiplication (and some primitives) ]
>>
>> 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.)
> 
> Thanks for the terse explanation; the formulas helped me to detect
> that the constants in Waldek's assembler code are the pre-computed
> reciprocals.
> 
> First I thought that there's a trick to avoid division of non-const
> expressions.
> 

For non-constant divisors, it's a bit more difficult!  If you are going 
to use the same divisor several times, it can be worth computing the 
scaled reciprocal, so that you only have one hard operation.  I believe 
that hardware floating point units do that anyway for division.