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.
- For n ≤ 100,000, the power tree method:
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)