strange exponentiation performance
nospam at nospam.com
Mon Nov 24 07:35:23 CET 2003
> I'm taking the liberty of rewriting your functions to stop trying to squash
> as much as they can on each line. It's important to do that if you want to
> modify the code quickly when experimenting.
> First you rediscovered the "left to right" binary exponentiation algorithm:
> When you tried to remove recursion from it, you rediscovered the "right to
> left" binary exponentiation algorithm:
Interesting. I suspected it wasn't a perfect unwrapping of the recursion,
because I didn't take the time to examine it carefully. Classic case of a
wonderful idea I had at 3:30 in the morning :)
> That's close to what Python's builtin ** does, but is missing an important
> speed trick (explained later). Note that h and f aren't really the *same*
> algorithm! f squares the current value of b on every trip through the loop.
> h does not. If you print out all the inputs to all the multiplications,
> you'll see that they're not at all the same.
> Your box is faster than mine. Here under 2.3.2 on Windows:
That means I win, right ;)
> exponentiation is a very hard problem; 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
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
> def q(b, e):
> if e == 0:
> return 1
> if e == 1:
> return b
> e2, numbits = e, 0
> while e2:
> e2 >>= 1
> numbits += 1
> assert numbits >= 2
> result = b
> mask = 1L << (numbits - 2)
> for dummy in range(numbits - 1):
> result *= result
> if e & mask:
> result *= b
> mask >>= 1
> return result
Now I understand what you mean about the right-left and left-right
versions. I only had a vague understanding before.
> That's bound to be a little faster than h on most inputs, because it
> also optimizes away multiplications by 1 (well, unless b happens to be
> 1). Let's see:
Might as well eliminate the multiplication by 1, for some reason I
assumed that could be optimized out somehow by the computer.
> Yup, those matter, but not a whale of a lot. The savings in
> multiplications by 1 is proportional to the number of 0 bits in the
> exponent. What *didn't* matter is whether it's recursive or iterative.
Yeah, I guess it's always the case: algorithm first, then optimize. I know
the rule, and I follow it when being paid (so as not to waste anyone's
money). When doing something more academic I always feel like I need to
break it down to the most simple operations so I understand what's going
on. To me, recursion hides what's going on to an extent, and I felt like I
didn't entirely understand the algorithm.
>> If my algorithm h() is better, why can't ** use a quick test to change
>> algorithms based on inputs? Or is mine better in all cases?
> See Knuth <wink>.
Uh-oh, another problem that's more difficult than meets the eye. I'll be
back with more questions in a few years I guess ;)
More information about the Python-list