diff options
| author | Tim Peters <tim.peters@gmail.com> | 2022-01-02 13:18:20 -0600 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2022-01-02 13:18:20 -0600 |
| commit | 863729e9c6f599286f98ec37c8716e982c4ca9dd (patch) | |
| tree | 8a993db961e57ce1208ed309bd40f92038517870 /Include | |
| parent | ce4d25f3cd0a1c6e65b64015140fb5e1397c8ac5 (diff) | |
| download | cpython3-863729e9c6f599286f98ec37c8716e982c4ca9dd.tar.gz | |
bpo-46218: Change long_pow() to sliding window algorithm (GH-30319)
* bpo-46218: Change long_pow() to sliding window algorithm
The primary motivation is to eliminate long_pow's reliance on that the number of bits in a long "digit" is a multiple of 5. Now it no longer cares how many bits are in a digit.
But the sliding window approach also allows cutting the precomputed table of small powers in half, which reduces initialization overhead enough that the approach pays off for smaller exponents too. Depending on exponent bit patterns, a sliding window may also be able to save some bigint multiplies (sometimes when at least 5 consecutive exponent bits are 0, regardless of their starting bit position modulo 5).
Note: boosting the window width to 6 didn't work well overall. It give marginal speed improvements for huge exponents, but the increased overhead (the small-power table needs twice as many entries) made it a loss for smaller exponents.
Co-authored-by: Oleg Iarygin <dralife@yandex.ru>
Diffstat (limited to 'Include')
| -rw-r--r-- | Include/cpython/longintrepr.h | 6 |
1 files changed, 0 insertions, 6 deletions
diff --git a/Include/cpython/longintrepr.h b/Include/cpython/longintrepr.h index ff4155f965..68dbf9c438 100644 --- a/Include/cpython/longintrepr.h +++ b/Include/cpython/longintrepr.h @@ -21,8 +21,6 @@ extern "C" { PyLong_SHIFT. The majority of the code doesn't care about the precise value of PyLong_SHIFT, but there are some notable exceptions: - - long_pow() requires that PyLong_SHIFT be divisible by 5 - - PyLong_{As,From}ByteArray require that PyLong_SHIFT be at least 8 - long_hash() requires that PyLong_SHIFT is *strictly* less than the number @@ -63,10 +61,6 @@ typedef long stwodigits; /* signed variant of twodigits */ #define PyLong_BASE ((digit)1 << PyLong_SHIFT) #define PyLong_MASK ((digit)(PyLong_BASE - 1)) -#if PyLong_SHIFT % 5 != 0 -#error "longobject.c requires that PyLong_SHIFT be divisible by 5" -#endif - /* Long integer representation. The absolute value of a number is equal to SUM(for i=0 through abs(ob_size)-1) ob_digit[i] * 2**(SHIFT*i) |