Talk:Exponentiation by squaring

I guess we should present the iterative version of this algorithm:

power(x,n) is computed as long as n is not negative
    assign 1 to result
    as long as n is positive
       assign x*x to x if n is even
       assign result*x to result if n is odd
       assign the truncated to next integer of n diveded by 2 to n
    return result

Robert Dober 2003-07-05 MEDST

Never mind, and there is even an error in my algorithm, really well done Robert, sorry for the noise :(

Robert Dober 2003-07-05 MEDST

Article incomplete

One aspect of this subject not mentioned is that this binary algorithm doesn't get to the exponent as fast as possible. For example:

1. x^62 => x^31*x^31
2. x^31 => x*x^30
3. x^30 => x^15*x^15
4. x^15 => x*x^14
5. x^14 => x^7*x^7
6. x^7 => x*x^6
7. x^6 => x^3*x^3
8. x^3 => x*x^2
9. x^2 => x*x

but assuming we remember all exponents we've previously created...

1. x*x => x^2
2. x^2*x^2 => x^4
3. x^4*x^4 => x^8
4. x^8*x^8 => x^16
5. x^4*x^16 => x^20
6. x^20*x^20 => x^40
7. x^20*x^40 => x^60
8. x^2*x^60 => x^62

This takes one step less. I have some more information on this if it would be interesting to have here. This isn't exactally exponentiating by squaring, but along the same lines.

---Jay

Yes, this would be interesting! Especially if there is (as I would expect) a quick systematic way to get at the fastest method, then this should be mentioned in the article as a variation. (And even if there's not a fast alternative algorithm, then this fact can still be mentioned.) Is this the addition chain exponentiation that Henrygb linked? -- Toby Bartels 19:58, 7 Aug 2004 (UTC)

Yes, both of these are considered addition chains. It is considered hard to generate minimal addition chains (where one takes the absolute least number of steps required to perform the exponentiation). In other words, there's a ton of setup that goes into generating these minimal chains, but they execute faster than any other addition chain. That makes them useless when only a single exponentiation is being performed, as so much time is spent in the setup. Binary addition chains (which is what this article is about) require no setup and are close enough to minimal to make them useful. Note that in the above example, there was only a one step difference. Such a binary addition chain executes somewhat more slowly than a minimal-length chain, but the time saved in skipping initial setup causes the net speed to be in the binary chain's favor. -- Vesta 09:12, 16 Aug 2004 (UTC)

As an aside, by definition exponentiation by squaring is a variation of addition chain exponentiation, not the other way around. :) -- Vesta 09:14, 16 Aug 2004 (UTC)

Iterative version useful?

It doesn't use recursion, which increases the speed even further.

Is it useful at all, though? To take the example from the article, x^1000000 requires 41 multiplications (and even fewer recursive calls than that). If you calculate x^1000000 for any x bigger than 1, the relative time spent on calls will be completely negligible. Fredrik | talk 16:40, 17 Feb 2005 (UTC)