strange exponentiation performance

Tim Peters tim.one at comcast.net
Mon Nov 24 13:23:27 EST 2003


[Tim]
>> ... Knuth Volume 2 has an extensive discussion of this ("Evaluation
>> of Powers"); another algorithm based on first factoring the exponent
>> (expressing it as a product of primes) is better "on average" than
>> either binary method, but sometimes loses to them.

[Jeff Davis]
> Ahh... I'm on vol. 1. I saw that it would be a while before I made it
> to page 100, so I actually loaned out vol. 2. I'll be getting that
> back now I guess :)

On second thought, Knuth may not be helpful here:  he's overwhelmingly
concerned with minimizing the number of multiplications performed, which is
"interesting" only if all multiplications take the same amount of time.
With ordinary care in coding, the left-to-right and right-to-left binary
exponentiation methods do exactly the same number of multiplications, so
there's no basis for favoring one based on that alone.

But large-int multiplications vary wildly in expense.  For example, it's
enormously more expensive to square a million-bit int than to multiply a
million-bit int by a 10-bit int.  The left-to-right and right-to-left
methods *do* differ in expense when that's taken into account too
(left-to-right is usually cheaper, in essence because each step either
squares or multiplies by the *original* base, while each step in R-to-L
either squares or multiplies two ever-growing intermediate results), and I
don't think Knuth talks about this complication.

Offhand, I don't know of anyone who does talk about it!  A few hours of
Googling on it may be an interesting project for you.  One reason it may be
hard to find info about this is that raw exponentiation of unbounded
integers has few practical use cases.  In real life, modular exponentiation
(Python's pow(a, b, c)) is overwhelmingly more common, and then all
intermediate results are bounded above by c, so there's an upper bound on
the expense of each multiply too, and then "all multiplications cost the
same" is closer to being true.  If a is very small compared to c, though, I
still expect L-to-R to have an advantage.

don't-forget-to-come-up-for-air<wink>-ly y'rs  - tim






More information about the Python-list mailing list