Talk:Knuth's power tree: Difference between revisions
(Dup?) |
(added comments about duplication of (exponentiation) of Rosetta Code tasks.) |
||
| Line 1: | 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) |
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) |
|||
Revision as of 17:49, 2 June 2015
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)