Anonymous user
Talk:Knuth's power tree: Difference between revisions
added comments about duplication of (exponentiation) of Rosetta Code tasks.
(Dup?) |
(added comments about duplication of (exponentiation) of Rosetta Code tasks.) |
||
Line 1:
==duplicate of addition-chain exponentiation?==
This looks like a duplicate of [[Addition-chain exponentiation]]. Perhaps some of the content here belongs on that page? --[[User:Rdm|Rdm]] ([[User talk: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. -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 17:49, 2 June 2015 (UTC)
| |||