[issue46218] Change long_pow() to sliding window algorithm

Change by Tim Peters : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___

[issue46218] Change long_pow() to sliding window algorithm

Tim Peters added the comment: New changeset 863729e9c6f599286f98ec37c8716e982c4ca9dd by Tim Peters in branch 'main': bpo-46218: Change long_pow() to sliding window algorithm (GH-30319) https://github.com/python/cpython/commit/863729e9c6f599286f98ec37c8716e982c4ca9dd --

[issue46218] Change long_pow() to sliding window algorithm

Tim Peters added the comment: Since cutting the window size by 1 cut the size of the dynamic precomputed table in half, the overhead of the sliding window method was correspondingly reduced. It can pay off at exponents of half the bit length now, so that threshold was also changed.

[issue46218] Change long_pow() to sliding window algorithm

Tim Peters added the comment: Nope, boosting the window size to 6 doesn't appear to really help at all, at least not on my box. Regardless of the window size, we have to do a bigint square for every bit position in the exponent. I don't know of any way to speed that (short of speeding

[issue46218] Change long_pow() to sliding window algorithm

Change by Tim Peters : -- keywords: +patch pull_requests: +28535 stage: needs patch -> patch review pull_request: https://github.com/python/cpython/pull/30319 ___ Python tracker

[issue46218] Change long_pow() to sliding window algorithm

New submission from Tim Peters : As discussed on python-dev, it would be nice to break long_pow()'s reliance on that the number of bits in a CPython long "digit" is a multiple of 5. Moving to the sliding-window algorithm would do that (it has to be able to cross digit boundaries to fill the