bpo-36887: add math.isqrt (GH-13244)
* Add math.isqrt function computing the integer square root.
* Code cleanup: remove redundant comments, rename some variables.
* Tighten up code a bit more; use Py_XDECREF to simplify error handling.
* Update Modules/mathmodule.c
Co-Authored-By: Serhiy Storchaka <storchaka@gmail.com>
* Update Modules/mathmodule.c
Use real argument clinic type instead of an alias
Co-Authored-By: Serhiy Storchaka <storchaka@gmail.com>
* Add proof sketch
* Updates from review.
* Correct and expand documentation.
* Fix bad reference handling on error; make some variables block-local; other tidying.
* Style and consistency fixes.
* Add missing error check; don't try to DECREF a NULL a
* Simplify some error returns.
* Another two test cases:
- clarify that floats are rejected even if they happen to be
squares of small integers
- TypeError beats ValueError for a negative float
* Documentation and markup improvements; thanks Serhiy for the suggestions!
* Cleaner Misc/NEWS entry wording.
* Clean up (with one fix) to the algorithm explanation and proof.
diff --git a/Doc/library/math.rst b/Doc/library/math.rst
index 49f932d..bf660ae 100644
--- a/Doc/library/math.rst
+++ b/Doc/library/math.rst
@@ -166,6 +166,20 @@
Return ``True`` if *x* is a NaN (not a number), and ``False`` otherwise.
+.. function:: isqrt(n)
+
+ Return the integer square root of the nonnegative integer *n*. This is the
+ floor of the exact square root of *n*, or equivalently the greatest integer
+ *a* such that *a*\ ² |nbsp| ≤ |nbsp| *n*.
+
+ For some applications, it may be more convenient to have the least integer
+ *a* such that *n* |nbsp| ≤ |nbsp| *a*\ ², or in other words the ceiling of
+ the exact square root of *n*. For positive *n*, this can be computed using
+ ``a = 1 + isqrt(n - 1)``.
+
+ .. versionadded:: 3.8
+
+
.. function:: ldexp(x, i)
Return ``x * (2**i)``. This is essentially the inverse of function
@@ -538,3 +552,6 @@
Module :mod:`cmath`
Complex number versions of many of these functions.
+
+.. |nbsp| unicode:: 0xA0
+ :trim: