[New-bugs-announce] [issue36887] Add integer square root, math.isqrt

[Mark Dickinson]

New submission from Mark Dickinson <dickinsm at 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 <report at bugs.python.org>
<https://bugs.python.org/issue36887>
_______________________________________