[fpc-devel] The "magic div" algorithm

[J. Gareth Moreton]

If the code breaks down to "x div 1000000000" (with 1000000000 as an 
explicit constant and x being a 64-bit integer), then yes it will.  If 
the divisor is a variable though, then it won't.  However, the "magic 
div" algorithm only works for numerators up to a given bit size; if the 
number exceeds it, you'll lose precision and risk getting an incorrect 
answer (a warning for if you want to try to implement the algorithm 
yourself).

Gareth aka. Kit

On 16/11/2021 17:52, Benito van der Zander via fpc-devel wrote:
> Hi,
>
> in my big decimal unit, I need to divide by 1000000000 all the time, 
> e.g. 
> https://github.com/benibela/bigdecimalmath/blob/master/bigdecimalmath.pas#L1324-L1325
>
> would the magic div help there much?
>
> Bye,
> Benito
> On 09.11.21 22:12, J. Gareth Moreton via fpc-devel wrote:
>>
>> This one for Marģers specifically,
>>
>> You'll be pleased to know that your insight has been partially 
>> implemented!
>>
>> https://gitlab.com/freepascal.org/fpc/source/-/merge_requests/51
>>
>> This only expands 32-bit divisions to 64-bit, since the smaller sizes 
>> requires more work at the node level, but is certainly possible and 
>> will happily continue to experiment with seeing if it can be 
>> implemented.  This was fun to do!
>>
>> The test "bench/bdiv.pp" (also "tests/test/cg/tmoddiv6.pp" which just 
>> includes the given file) is my benchmark test for division and 
>> modulus operations if anyone wants to see if they can make the 
>> fundamental routine faster on any platform.
>>
>> Gareth aka. Kit
>>
>> On 24/08/2021 20:14, Marģers . via fpc-devel wrote:
>>> I came up with even shorter variant of div
>>> example
>>> function teDWordDivBy7_v4( divided : dword):dword; assembler; 
>>> nostackframe;
>>> asm
>>>      mov ecx,divided
>>>      mov rax,2635249153693862181
>>>      mul rcx
>>>      mov eax,edx
>>> end;
>>>
>>> current version for comparison
>>>
>>> function teDWordDivBy7_v0( divided : dword):dword; assembler; 
>>> nostackframe;
>>> asm
>>>      mov ecx,divided
>>>      mov eax,613566757
>>>      mul ecx
>>>      add edx,ecx
>>>      rcr edx,1
>>>      shr edx,2
>>>      mov eax,edx
>>> end;
>>>
>>>             	
>>>
>>>
>>> _______________________________________________
>>> fpc-devel maillist  -fpc-devel at lists.freepascal.org
>>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>>
>> <https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
>> 	Virus-free. www.avast.com 
>> <https://www.avast.com/sig-email?utm_medium=email&utm_source=link&utm_campaign=sig-email&utm_content=emailclient> 
>>
>>
>> <#DAB4FAD8-2DD7-40BB-A1B8-4E2AA1F9FDF2>
>>
>> _______________________________________________
>> fpc-devel maillist  -fpc-devel at lists.freepascal.org
>> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
>
> _______________________________________________
> fpc-devel maillist  -fpc-devel at lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

-- 
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20211116/a4e9d1de/attachment.htm>