New submission from Jurjen N.E. Bos <j...@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 <rep...@bugs.python.org> <https://bugs.python.org/issue42911> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
