Author jneb
Recipients jneb
Date 2021-01-12.14:52:13
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1610463140.75.0.177431925065.issue42911@roundup.psfhosted.org>
In-reply-to
Content
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
History
Date User Action Args
2021-01-12 14:52:20jnebsetrecipients: + jneb
2021-01-12 14:52:20jnebsetmessageid: <1610463140.75.0.177431925065.issue42911@roundup.psfhosted.org>
2021-01-12 14:52:20jneblinkissue42911 messages
2021-01-12 14:52:20jnebcreate