Author mark.dickinson
Recipients mark.dickinson
Date 2019-05-11.13:46:55
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1557582416.09.0.555439074551.issue36887@roundup.psfhosted.org>
In-reply-to
Content
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
History
Date User Action Args
2019-05-11 13:46:56mark.dickinsonsetrecipients: + mark.dickinson
2019-05-11 13:46:56mark.dickinsonsetmessageid: <1557582416.09.0.555439074551.issue36887@roundup.psfhosted.org>
2019-05-11 13:46:56mark.dickinsonlinkissue36887 messages
2019-05-11 13:46:55mark.dickinsoncreate