bpo-36957: Speed up math.isqrt (#13405)

* 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

* Add fast path for small inputs. Needs tests.

* Speed up isqrt for n >= 2**64 as well; add extra tests.

* Reduce number of test-cases to avoid dominating the run-time of test_math.

* Don't perform unnecessary extra iterations when computing c_bit_length.

* Abstract common uint64_t code out into a separate function.

* Cleanup.

* Add a missing Py_DECREF in an error branch. More cleanup.

* Update Modules/mathmodule.c

Add missing `static` declaration to helper function.

Co-Authored-By: Serhiy Storchaka <storchaka@gmail.com>

* Add missing backtick.

0 files changed, 0 insertions, 0 deletions