[New-bugs-announce] [issue43053] Speed up math.isqrt, again

[Juraj Sukop]

New submission from Juraj Sukop <juraj.sukop at gmail.com>:

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)`.

----------
components: Extension Modules
files: isqrt_2.py
messages: 385848
nosy: juraj.sukop
priority: normal
severity: normal
status: open
title: Speed up math.isqrt, again
type: performance
versions: Python 3.8
Added file: https://bugs.python.org/file49770/isqrt_2.py

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue43053>
_______________________________________