classification
Title: Add integer square root, math.isqrt
Type: enhancement Stage: resolved
Components: Extension Modules Versions: Python 3.8
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: mark.dickinson, rhettinger, serhiy.storchaka, steven.daprano, tim.peters
Priority: normal Keywords: patch

Created on 2019-05-11 13:46 by mark.dickinson, last changed 2019-05-18 13:23 by mark.dickinson. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 13244 merged mark.dickinson, 2019-05-11 13:58
Messages (13)
msg342187 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 13:46
The integer square root[1] is a common number-theoretic primitive, useful for example in primality testing. This is something I've had to code up myself multiple times, and is also something that's quite easy to get wrong, or implement in a way that's inefficient for large inputs.

I propose adding a math module function `math.isqrt` implementing the integer square root. Like `math.gcd`, it should accept any integer-like object `n` (i.e., `int`s and anything implementing `__index__`), and for nonnegative inputs, should return the largest int `a` satisfying `a * a <= n`.

Negative inputs should give a ValueError; non-integer inputs (including `float`s) should give a TypeError.

I'll create a PR shortly with a basic implementation; optimizations can happen later.


[1] https://en.wikipedia.org/wiki/Integer_square_root
msg342188 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-05-11 13:59
+1, but I propose to add it to the new imath module and move also factorial() and gcd() to it. New binomial() or comb() function (issue35431) should be added in imath too.
msg342189 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 14:10
FTR (not for Serhiy, but for others reading this), here's the previous discussion of the possibility of adding an imath module.

   https://mail.python.org/pipermail/python-ideas/2018-July/051917.html

While I'm happy for this to go in either math or a new imath module, I'm a bit sceptical that at this point we're going to get a useful imath module together in time for 3.8 (and I don't have bandwidth to do the imath work myself). How about we put it in math for now, and if we get around to imath before the 3.8b1, I'm happy to have it move from math to imath?
msg342190 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-05-11 14:29
I am wondering whether int(sqrt(float(n))) can be used as a good initial approximation.
msg342191 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 14:33
> I am wondering whether int(sqrt(float(n))) can be used as a good initial approximation.

It can, but I'd prefer to avoid floating-point arithmetic (we don't have any guarantees about the accuracy of sqrt, so you'd always need a check and a fallback for the case where sqrt isn't accurate enough), and there are other purely-integer-based ways to produce a fast initial approximation. I do have some plans to add optimizations, but wanted to get the basic algorithm in first.
msg342192 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-05-11 14:35
What do you think about adding two integer square root functions -- for the largest int `a` satisfying `a * a <= n` and for the smallest int `a` satisfying `a * a >= n`? The latter case is also often encounter in practice. For example, this is the size of the smallest square table in which we can place n items, not more than one per cell. We could call these functions fllorsqtr() and ceilsqrt() (if there are no better standard names).
msg342193 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 14:40
> for the smallest int `a` satisfying `a * a >= n`

I'd spell that as `1 + isqrt(n - 1)`. I'd prefer to keep things simple and just add the one building block, rather than adding multiple variants.
msg342194 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 14:41
Some more discussion of possible algorithms and variations here: https://github.com/mdickinson/snippets/blob/master/notebooks/Integer%20square%20roots.ipynb

(not sure why the LaTeX isn't all rendering properly at the bottom in the GitHub view; it's fine in my local notebook).
msg342203 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-05-11 16:05
> I'd spell that as `1 + isqrt(n - 1)`.

Could you please add this in the documentation?
msg342205 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-11 16:13
> Could you please add this in the documentation?

Yes, definitely!
msg342239 - (view) Author: Steven D'Aprano (steven.daprano) * (Python committer) Date: 2019-05-12 04:41
Yes please for this!

The two usual versions are isqrt and nsqrt:

isqrt(n) = largest integer ≤ √n

nsqrt(n) = closest integer to √n

although to be honest I'm not sure what use cases there are for nsqrt.
msg342419 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-05-14 02:37
+1 from me!  I'm tired of re-inventing this too :-)

Agree with every point Mark made.

Just in passing, noting a triviality:  for the ceiling, `1 + isqrt(n - 1)` fails when `n` is zero.

But I've never had a use for the ceiling here, or for "nearest" - just the floor.  Also for `iroot(n, k)` for k'th root floors with k > 2, but that too can wait.
msg342793 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-05-18 11:29
New changeset 73934b9da07daefb203e7d26089e7486a1ce4fdf by Mark Dickinson in branch 'master':
bpo-36887: add math.isqrt (GH-13244)
https://github.com/python/cpython/commit/73934b9da07daefb203e7d26089e7486a1ce4fdf
History
Date User Action Args
2019-05-18 13:23:17mark.dickinsonsetstatus: open -> closed
resolution: fixed
stage: patch review -> resolved
2019-05-18 11:29:54mark.dickinsonsetmessages: + msg342793
2019-05-14 02:37:14tim.peterssetnosy: + tim.peters
messages: + msg342419
2019-05-12 04:52:10xtreaksetnosy: + rhettinger
2019-05-12 04:41:05steven.dapranosetnosy: + steven.daprano
messages: + msg342239
2019-05-11 16:13:36mark.dickinsonsetmessages: + msg342205
2019-05-11 16:05:25serhiy.storchakasetmessages: + msg342203
2019-05-11 14:41:19mark.dickinsonsetmessages: + msg342194
2019-05-11 14:40:06mark.dickinsonsetmessages: + msg342193
2019-05-11 14:35:49serhiy.storchakasetmessages: + msg342192
2019-05-11 14:33:21mark.dickinsonsetmessages: + msg342191
2019-05-11 14:29:03serhiy.storchakasetmessages: + msg342190
2019-05-11 14:10:26mark.dickinsonsetmessages: + msg342189
2019-05-11 13:59:49serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg342188
2019-05-11 13:58:06mark.dickinsonsetkeywords: + patch
stage: needs patch -> patch review
pull_requests: + pull_request13156
2019-05-11 13:46:56mark.dickinsoncreate