[issue42911] Addition chains for pow saves 10 % time!

Jurjen N.E. Bos added the comment: Well, measurements show that it saves more time than I thought (sometimes over 20%!), because there are other ways in which it saves time; I am quite happy with that. In the code I needed functions _Py_bit_length64 and _Py_bit_count64. I thought these

[issue42911] Addition chains for pow saves 10 % time!

Change by Jurjen N.E. Bos : -- keywords: +patch pull_requests: +23032 stage: -> patch review pull_request: https://github.com/python/cpython/pull/24206 ___ Python tracker ___

[issue42911] Addition chains for pow saves 10 % time!

Change by Serhiy Storchaka : -- nosy: +serhiy.storchaka ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue42911] Addition chains for pow saves 10 % time!

Jurjen N.E. Bos added the comment: Some more information for the interested: The algorithm I made tries to smoothly change the"chunk size" with growing length of the exponent. So the exponents that win the most (up to 14% fewer multiplication) are the long exponents that are just shorter

[issue42911] Addition chains for pow saves 10 % time!

Change by Guido van Rossum : -- nosy: +mark.dickinson, tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue42911] Addition chains for pow saves 10 % time!

New submission from Jurjen N.E. Bos : 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