Talk:Knuth's power tree

duplicate of addition-chain exponentiation?

This looks like a duplicate of Addition-chain exponentiation. Perhaps some of the content here belongs on that page? --Rdm (talk) 11:46, 2 June 2015 (UTC)

---

Knuth's power tree   isn't a duplicate of   addition-chain exponentiation,   Knuth's power tree is much simpler to compute, and in almost all of the exponentiation process, is different than addition-chain exponentiation (but yields the same result, of course, albeit in a different way).

In the Rosetta Code task   Addition-chain exponentiation,   there's a lot of reference to the   binary   method (also known elsewhere as   the factor method)   which, as noted in the preamble text of this Rosetta Code task:

For   n   ≤ 100,000,   the power tree method:

•   bests the factor method   88,803   times,
•   ties   11,191   times,
•   loses   6   times.

From this, it can be seen that Knuth's power tree isn't always the best algorithm for exponentiation (as compared to   the factor method),   but it's better over 88% of the time.

Knuth's power tree probably resembles addition-chain exponentiation as much as calculation of primes via   trial division   versus   Sieve of Eratosthenes,   they have the same result, but with different strategies and complexity. -- Gerard Schildberger (talk) 17:49, 2 June 2015 (UTC)

Ah, my mistake.

Triggered, on re-reading, by an utter lack of description of the algorithm on the page itself, combined with [for me] unfamiliar (and unlinked) terms for familiar concepts (like "factor method" - technically all of these approaches are "factor methods" so without some definition the term winds up being ambiguous). And I don't have a copy of Knuth's book handy. I guess I am supposed to reverse engineer one of the linked implementations? --Rdm (talk) 18:13, 2 June 2015 (UTC)