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)

I have Knuth's Vol. 2 book, but the algorithm is way beyond my ability to explain it or paraphrase it, or even parrot it. (My utter is bigger than your utter, and I have a book for help). Even if I could explain it, Dr. Knuth's explanation of pretty detailed and extensive. I've read (and re-read) the particular chapter and still don't know it well enough to explain it. I was thinking about quoting the text wholesale, but I didn't want to push that particular envelope. Perhaps someone with a much better mathematics background could dive in that pool and illuminate the process (well, Dr. Knuth did, but I'm still a bit mystified and unilluminated). I was hoping that the ~~two~~ several computer programming examples (as referenced by the links) would provide enough insight to code other computer programming language examples (entries). -- Gerard Schildberger (talk) 19:33, 2 June 2015 (UTC)

The factor method or binary factor method or more simply binary method, is as follows (as mentioned in Knuth's book):

(Note that this isn't a description of Knuth's power tree method)

For a positive integer n (for an exponent):

express n in binary form (ignore any leading zeroes)
substitute each 1 by the (two) letters SX
substitute each 0 by the (single) letter S
remove the (two) leading (on the left) letters SX

We now have a method (or "rule") for computing xⁿ.

(From left to right):

S means to square the number,
X means to multiply the number by x.

══════════ An illustrative example of the binary factor method ══════════

for the power 23,
it's binary representation is 10111,
so the following sequence is: SX S SX SX SX.

Now, remove the leading (left) SX two letters,
resulting in S SX SX SX.

So the rule (sequence) is:

square
square
multiple by x
square
multiple by x
square
multiple by x

Or, in wording it in another way, we have computed:

x²
x⁴
x⁵
x¹⁰
x¹¹
x²²
x²³

-- Gerard Schildberger (talk) 19:33, 2 June 2015 (UTC)

Yes, but it's the power tree algorithm which we need here. Actually, I found https://comeoncodeon.wordpress.com/2009/03/02/evaluation-of-powers/ which indicates that the factor method is different from the binary method. I'm studying its description of the power tree algorithm now. --Rdm (talk) 21:59, 2 June 2015 (UTC)