# Talk:Knuth's power tree

## duplicate of addition-chain exponentiation?[edit]

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

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)

- 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

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

- express

We now have a method (or "rule") for computing x^{n}.

(From left to right):

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

- S means to

** ══════════ 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
^{2} - x
^{4} - x
^{5} - x
^{10} - x
^{11} - x
^{22} - x
^{23}

- 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)