I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Talk:Knuth's power tree

From Rosetta Code

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.

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   xn.

(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:

  •   x2
  •   x4
  •   x5
  •   x10
  •   x11
  •   x22
  •   x23



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