Author juraj.sukop
Recipients juraj.sukop
Date 2021-01-28.08:03:26
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1611821006.77.0.580238316666.issue43053@roundup.psfhosted.org>
In-reply-to
Content
This is a follow up to https://bugs.python.org/issue36887 and https://bugs.python.org/issue36957 .

The new `isqrt` is remarkably simple but it does not split the number at hand optimally. Ideally one would want to have 2n/n division everywhere but since the last iteration takes as much effort as all of the iterations before it this is what the attached code focuses on.

At least in my testing the `isqrt_2` code below improved the performance by 50% (3s down to 2s, for example) and, if used, perhaps the original `isqrt` could do without the final correction `a - (a*a > n)`.
History
Date User Action Args
2021-01-28 08:03:26juraj.sukopsetrecipients: + juraj.sukop
2021-01-28 08:03:26juraj.sukopsetmessageid: <1611821006.77.0.580238316666.issue43053@roundup.psfhosted.org>
2021-01-28 08:03:26juraj.sukoplinkissue43053 messages
2021-01-28 08:03:26juraj.sukopcreate