Challenge: optimizing isqrt
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
More information about the Python-list