[New-bugs-announce] [issue46218] Change long_pow() to sliding window algorithm

[Tim Peters]

New submission from Tim Peters <tim at python.org>:

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 current window), and would be better on some other counts too: the precomputed table can be half the size (or we can add an extra bit to the window for the same table size), and it can - depending on exponent bit patterns - sometimes reduce the number of multiplies needed too.

So I intend to do that, and bump the window size from 5 to 6 (which would yield a significant, although modest, speed improvement for giant-exponent cases).

----------
assignee: tim.peters
components: Interpreter Core
messages: 409446
nosy: tim.peters
priority: normal
severity: normal
stage: needs patch
status: open
title: Change long_pow() to sliding window algorithm
type: performance
versions: Python 3.11

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue46218>
_______________________________________