Add integer square root, math.isqrt

[mdickinson]

BPO	36887
Nosy	@tim-one, @rhettinger, @mdickinson, @stevendaprano, @serhiy-storchaka
PRs	bpo-36887: add math.isqrt #13244

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = <Date 2019-05-18.13:23:17.541>
created_at = <Date 2019-05-11.13:46:56.062>
labels = ['extension-modules', 'type-feature', '3.8']
title = 'Add integer square root, math.isqrt'
updated_at = <Date 2019-05-18.13:23:17.540>
user = 'https://github.com/mdickinson'

bugs.python.org fields:

activity = <Date 2019-05-18.13:23:17.540>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2019-05-18.13:23:17.541>
closer = 'mark.dickinson'
components = ['Extension Modules']
creation = <Date 2019-05-11.13:46:56.062>
creator = 'mark.dickinson'
dependencies = []
files = []
hgrepos = []
issue_num = 36887
keywords = ['patch']
message_count = 13.0
messages = ['342187', '342188', '342189', '342190', '342191', '342192', '342193', '342194', '342203', '342205', '342239', '342419', '342793']
nosy_count = 5.0
nosy_names = ['tim.peters', 'rhettinger', 'mark.dickinson', 'steven.daprano', 'serhiy.storchaka']
pr_nums = ['13244']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue36887'
versions = ['Python 3.8']

[mdickinson]

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., ints 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 floats) 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

[serhiy-storchaka]

+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 (bpo-35431) should be added in imath too.

[mdickinson]

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?

[serhiy-storchaka]

I am wondering whether int(sqrt(float(n))) can be used as a good initial approximation.

[mdickinson]

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.

[serhiy-storchaka]

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

[mdickinson]

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.

[mdickinson]

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

[serhiy-storchaka]

I'd spell that as 1 + isqrt(n - 1).

Could you please add this in the documentation?

[mdickinson]

Could you please add this in the documentation?

Yes, definitely!

[stevendaprano]

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.

[tim-one]

+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.

[mdickinson]

New changeset 73934b9 by Mark Dickinson in branch 'master':
bpo-36887: add math.isqrt (GH-13244)
73934b9