]> granicus.if.org Git - python/commit
bpo-36957: Speed up math.isqrt (#13405)
authorMark Dickinson <mdickinson@enthought.com>
Sun, 19 May 2019 16:51:56 +0000 (17:51 +0100)
committerGitHub <noreply@github.com>
Sun, 19 May 2019 16:51:56 +0000 (17:51 +0100)
commit5c08ce9bf712acbb3f05a3a57baf51fcb534cdf0
treef31a368cd3f31951303766f605111f9589612d44
parent7c59362a15dfce538512ff1fce4e07d33a925cfb
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.
Lib/test/test_math.py
Modules/mathmodule.c