[issue36887] Add integer square root, math.isqrt

Change by Mark Dickinson : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ __

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: New changeset 73934b9da07daefb203e7d26089e7486a1ce4fdf by Mark Dickinson in branch 'master': bpo-36887: add math.isqrt (GH-13244) https://github.com/python/cpython/commit/73934b9da07daefb203e7d26089e7486a1ce4fdf -- _

[issue36887] Add integer square root, math.isqrt

Tim Peters added the comment: +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

[issue36887] Add integer square root, math.isqrt

Change by Karthikeyan Singaravelan : -- nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: htt

[issue36887] Add integer square root, math.isqrt

Steven D'Aprano added the comment: 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. -- nosy: +steven.daprano _

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: > Could you please add this in the documentation? Yes, definitely! -- ___ Python tracker ___ ___

[issue36887] Add integer square root, math.isqrt

Serhiy Storchaka added the comment: > I'd spell that as `1 + isqrt(n - 1)`. Could you please add this in the documentation? -- ___ Python tracker ___

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: > 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. -- ___ Python tr

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: 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 m

[issue36887] Add integer square root, math.isqrt

Serhiy Storchaka added the comment: 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

[issue36887] Add integer square root, math.isqrt

Serhiy Storchaka added the comment: I am wondering whether int(sqrt(float(n))) can be used as a good initial approximation. -- ___ Python tracker ___

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: > 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 t

[issue36887] Add integer square root, math.isqrt

Mark Dickinson added the comment: 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 ima

[issue36887] Add integer square root, math.isqrt

Serhiy Storchaka added the comment: +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. -- nosy: +serhiy.storchaka ___ Python t

[issue36887] Add integer square root, math.isqrt

Change by Mark Dickinson : -- keywords: +patch pull_requests: +13156 stage: needs patch -> patch review ___ Python tracker ___ ___ P

[issue36887] Add integer square root, math.isqrt

New submission from Mark Dickinson : 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 inef