View source for 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? --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 11:46, 2 June 2015 (UTC)

-----

''Knuth's power tree'' &nbsp; isn't a duplicate of &nbsp; ''addition-chain exponentiation'', &nbsp; 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 &nbsp; ''Addition-chain exponentiation'', &nbsp; there's a lot of reference to the &nbsp; ''binary'' &nbsp; method (also known elsewhere as &nbsp; ''the factor method'') &nbsp; which, as noted in the preamble text of this Rosetta Code task:

:: For &nbsp; ''n'' &nbsp; ≤ 100,000, &nbsp; the power tree method:
::::* &nbsp; bests the factor method &nbsp; 88,803 &nbsp; times,
::::* &nbsp; ties &nbsp; 11,191 &nbsp; times,
::::* &nbsp; loses &nbsp; 6 &nbsp; times.

From this, it can be seen that Knuth's power tree isn't always the best algorithm for exponentiation (as compared to &nbsp; ''the factor method''), &nbsp; 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 &nbsp; ''trial division'' &nbsp; versus &nbsp; ''Sieve of Eratosthenes'', &nbsp; 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)

: 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? --[[User:Rdm|Rdm]] ([[User talk: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. &nbsp; (My utter is bigger than your utter, and I have a book for help). &nbsp; Even if I could explain it, Dr. Knuth's explanation of pretty detailed and extensive. &nbsp; I've read (and re-read) the particular chapter and still don't know it well enough to explain it. &nbsp; I was thinking about quoting the text wholesale, but I didn't want to push that particular envelope. &nbsp; Perhaps someone with a much better mathematics background could dive in that pool and illuminate the process &nbsp; (well, Dr. Knuth did, but I'm still a bit mystified and unilluminated). &nbsp; I was hoping that the <strike> two </strike> &nbsp; several computer programming examples (as referenced by the links) would provide enough insight to code other computer programming language examples (entries). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:33, 2 June 2015 (UTC)

-----

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

(Note that this &nbsp; <u>isn't</u> &nbsp; a description of Knuth's power tree method)


For a positive integer &nbsp; ''n'' &nbsp; (for an exponent):
::* &nbsp; express &nbsp; ''n'' &nbsp; in binary form &nbsp; (ignore any leading zeroes)
::* &nbsp; substitute each &nbsp; <big>1</big> &nbsp; by the (two) letters &nbsp; <big>SX</big>
::* &nbsp; substitute each &nbsp; <big>0</big> &nbsp; by the (single) letter &nbsp; <big>S</big>
::* &nbsp; remove the (two) leading (on the left) letters &nbsp; <big>SX</big>

We now have a method (or "rule") for computing &nbsp; <big>x<sup>n</sup></big>. <br> 

(From left to right): 

::* &nbsp; <big>S</big> &nbsp; means to &nbsp; ''square'' &nbsp; the number, 
::* &nbsp; <big>X</big> &nbsp; means to &nbsp; ''multiply'' &nbsp; the number by &nbsp; <big>x</big>. 
<br><br>

''' ══════════ &nbsp; An illustrative example of the binary factor method &nbsp; ══════════ '''

for the power &nbsp; <big>23</big>,
<br>it's binary representation is &nbsp; <big>10111</big>,
<br>so the following sequence is: &nbsp; <big>SX S SX SX SX</big>.

Now, remove the leading (left) &nbsp; <big>SX</big> &nbsp; two letters,
<br>resulting in &nbsp; <big>S SX SX SX</big>. <br>

So the rule (sequence) is:
:::* &nbsp; square
:::* &nbsp; square
:::* &nbsp; multiple by &nbsp; <big>x</big>
:::* &nbsp; square
:::* &nbsp; multiple by &nbsp; <big>x</big>
:::* &nbsp; square
:::* &nbsp; multiple by &nbsp; <big>x</big>

Or, in wording it in another way, we have computed:
::::* &nbsp; <big>x<sup>2</sup></big>
::::* &nbsp; <big>x<sup>4</sup></big>
::::* &nbsp; <big>x<sup>5</sup></big>
::::* &nbsp; <big>x<sup>10</sup></big>
::::* &nbsp; <big>x<sup>11</sup></big>
::::* &nbsp; <big>x<sup>22</sup></big>
::::* &nbsp; <big>x<sup>23</sup></big>

<br><br> -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 21:59, 2 June 2015 (UTC)