[New-bugs-announce] [issue46258] Minor algorithmic improvements for math.isqrt

[Mark Dickinson]

New submission from Mark Dickinson <dickinsm at gmail.com>:

There are a couple of minor algorithmic improvements possible for the math.isqrt fast path (which is used for nonnegative integers smaller than 2**64). On my machine those improvements produce a little over a 10% speedup.

The current algorithm for values under 2**64 involves exactly four division instructions, corresponding to four Newton steps. The proposal is to:

- 1. Replace the first division with a table lookup. The necessary table is extremely small: 12 entries at one byte per entry.
- 2. Arrange for the return type of the _approximate_sqrt helper function to be uint32_t rather than uint64_t. That means that the correction step only involves a 32-bit-by-32-bit multiplication, not a 64-bit-by-64-bit multiplication.

The second part is a bit subtle: the input to _approximate_sqrt is a 64-bit integer `n` in the range [2**62, 2**64). Barring any overflow, the output `u` is guaranteed to satisfy `(u-1)**2 < n < (u+1)**2`. That implies that `(u-1)**2 < 2**64`, from which it follows that `u <= 2**32`. So the only possible case where `u` might overflow a `uint32_t` is when `u == 2**32`. But from the earlier inequality, that can only happen if `n > (2**32 - 1)**2`, and in that case the top 31 bits of `n` are completely determined and since the first steps of the algorithm only depend on the topmost bits of `n`, it's easy to follow through the algorithm and see that it's not possible for `u` to be `2**32` in that case. (We always get `u = 128` from the lookup, followed by `u = 255` after the first division, then `u = 65536` after the second.)

----------
components: Extension Modules
messages: 409693
nosy: mark.dickinson
priority: normal
severity: normal
stage: commit review
status: open
title: Minor algorithmic improvements for math.isqrt
type: performance
versions: Python 3.11

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