New submission from Mark Dickinson <dicki...@gmail.com>:
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 ---------- assignee: mark.dickinson components: Extension Modules messages: 342187 nosy: mark.dickinson priority: normal severity: normal stage: needs patch status: open title: Add integer square root, math.isqrt type: enhancement versions: Python 3.8 _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue36887> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
