Anonymous user
Talk:Knuth's power tree: Difference between revisions
→duplicate of addition-chain exponentiation?: explaining the binary factor method.
(→duplicate of addition-chain exponentiation?: explaining the binary factor method.) |
|||
Line 21:
: 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. (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 programming examples (as referenced by the links) would provide enough insight to code other language examples (entries). -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk: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):
For a positive integer ''n'' (for an exponent):
::* express ''n'' in binary form (ignore any leading zeroes)
::* substitute each <big>1</big> by the (two) letters <big>SX</big>
::* substitute each <big>0</big> by the (single) letter <big>S</big>
::* remove the (two) leading (on the left) letters <big>SX</big>
We now have a method (or "rule") for computing <big>x<sup>n</sup></big>. <br>
(From left to right):
::* <big>S</big> means to ''square'' the number,
::* <big>X</big> means to ''multiply'' the number by <big>x</big>.
<br><br>
''' ══════════ An illustrative example of the binary factor method ══════════ '''
for the power <big>23</big>,
<br>it's binary representation is <big>10111</big>,
<br>so the following sequence is: <big>SX S SX SX SX</big>.
Now, remove the leading (left) <big>SX</big> two letters,
<br>resulting in <big>S SX SX SX</big>. <br>
So the rule (sequence) is:
:::* square
:::* square
:::* multiple by <big>x</big>
:::* square
:::* multiple by <big>x</big>
:::* square
:::* multiple by <big>x</big>
Or, in wording it in another way, we have computed:
::::* <big>x<sup>2</sup></big>
::::* <big>x<sup>4</sup></big>
::::* <big>x<sup>5</sup></big>
::::* <big>x<sup>10</sup></big>
::::* <big>x<sup>22</sup></big>
::::* <big>x<sup>23</sup></big>
<br><br> -- [[User:Gerard Schildberger|Gerard Schildberger]] ([[User talk:Gerard Schildberger|talk]]) 19:33, 2 June 2015 (UTC)
| |||