[New-bugs-announce] [issue42911] Addition chains for pow saves 10 % time!

[Jurjen N.E. Bos]

New submission from Jurjen N.E. Bos <jneb at users.sourceforge.net>:

When looking at the code of pow() with integer exponent, I noticed there is a hard boundary between the binary and "fiveary" (actually 32-ary) computations. Also, the fiveary wasn't really optimal.

So I wrote a proof of concept version of long_pow that dynamically uses addition chains!
It does save over 10 % of multiplications for exponents from 20 to a few hundred bits, and then the saving go down to a few percent for very long numbers. It does not take much more memory nor time for any argument combination I checked.
I tested it on 3.8rc1, but I am planning to port it to 3.10. This is a bit difficult, since *lots* of code around it changed, and I only have Windows 7. However, I'll keep you posted.
See https://github.com/jneb/cpython/tree/38_fast_pow

----------
components: Interpreter Core
files: longobject.c
messages: 384949
nosy: jneb
priority: normal
severity: normal
status: open
title: Addition chains for pow saves 10 % time!
type: performance
versions: Python 3.10
Added file: https://bugs.python.org/file49737/longobject.c

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