Challenge: optimizing isqrt

Christian Gollwitzer auriocus at gmx.de
Sat Nov 1 09:38:12 CET 2014


Am 01.11.14 09:33, schrieb Chris Angelico:
> On Sat, Nov 1, 2014 at 7:25 PM, Christian Gollwitzer <auriocus at gmx.de> wrote:
>>> Part of the point of that algorithm is that it never uses FP, and is
>>> therefore not limited by FP restrictions.
>>
>>
>> which are???
>
> Most notably, the inability to represent every integer beyond 2**53,
> and the inability to represent any integer beyond 2**1024. This
> algorithm should work fine with any positive integer.
>
  OK so you did not bother to look at my proposed alternative 
implementation. If I understood Steven correctly, he wanted to speed up 
the original isqrt algorithm by using FP when this is possible. I have 
shown how to do it for n<2**1022 (maybe 2**1024, I'm to lean to check 
it). I admit that there is some microoptimizatio left, e.g. the first 
division is done twice, the comparison should be bits>1022, not n>2*1022 
etc.

	Christian




More information about the Python-list mailing list