78 lines
5.2 KiB
Text
78 lines
5.2 KiB
Text
(Knuth's power tree is used for computing <big><big>x<sup>n</sup></big></big> efficiently.)<br>
|
|
|
|
|
|
;Task:
|
|
Compute and show the list of Knuth's power tree integers necessary for the computation of:
|
|
|
|
::* <big><big>x<sup>n</sup></big></big> for any real <big><big>x</big></big> and any non-negative integer <big>n</big>.
|
|
|
|
|
|
|
|
Then, using those integers, calculate and show the exact values of (at least) the integer powers below:
|
|
|
|
::* <big>2<sup>n</sup></big> where n ranges from 0 ──► 17 (inclusive) <br>
|
|
::* <big>3<sup>191</sup></big>
|
|
::* <big>1.1<sup>81</sup></big>
|
|
|
|
|
|
A ''zero'' power is often handled separately as a special case.
|
|
|
|
Optionally, support negative integer powers.
|
|
|
|
|
|
;Example:
|
|
An example of a small power tree for some low integers:
|
|
<pre>
|
|
1
|
|
\
|
|
2
|
|
___________________________________________/ \
|
|
/ \
|
|
3 4
|
|
/ \____________________________________ \
|
|
/ \ \
|
|
5 6 8
|
|
/ \____________ / \ \
|
|
/ \ / \ \
|
|
7 10 9 12 16
|
|
/ //\\ │ │ /\
|
|
/ _____// \\________ │ │ / \
|
|
14 / / \ \ │ │ / \
|
|
/│ \ 11 13 15 20 18 24 17 32
|
|
/ │ \ │ /\ /\ │ /\ │ /\ │
|
|
/ │ \ │ / \ / \ │ / \ │ / \ │
|
|
19 21 28 22 23 26 25 30 40 27 36 48 33 34 64
|
|
│ /\ /│\ │ │ /\ │ /\ /│\ │ /\ /│\ │ │ /\
|
|
│ / \ / │ \ │ │ / \ │ / \ / │ \ │ / \ / │ \ │ │ / \
|
|
38 35 42 29 31 56 44 46 39 52 50 45 60 41 43 80 54 37 72 49 51 96 66 68 65 128
|
|
</pre>
|
|
Where, for the power <big>43</big>, following the tree "downwards" from <big>1</big>:
|
|
::* (for 2) compute square of <big>X</big>, store <big>X<sup>2</sup></big>
|
|
::* (for 3) compute <big>X</big> * <big>X<sup>2</sup></big>, store <big>X<sup>3</sup></big>
|
|
::* (for 5) compute <big>X<sup>3</sup></big> * <big>X<sup>2</sup></big>, store <big>X<sup>5</sup></big>
|
|
::* (for 10) compute square of <big>X<sup>5</sup></big>, store <big>X<sup>10</sup></big>
|
|
::* (for 20) compute square of <big>X<sup>10</sup></big>, store <big>X<sup>20</sup></big>
|
|
::* (for 40) compute square of <big>X<sup>20</sup></big>, store <big>X<sup>40</sup></big>
|
|
::* (for 43) compute <big>X<sup>40</sup></big> * <big>X<sup>3</sup></big> (result).
|
|
|
|
Note that for every even integer (in the power tree), one just squares the previous value.
|
|
|
|
For an odd integer, multiply the previous value with an appropriate odd power of <big>X</big> (which was previously calculated).
|
|
For the last multiplication in the above example, it would be <big>(43-40)</big>, or <big>3</big>. <br>
|
|
|
|
According to Dr. Knuth (see below), computer tests have shown that this power tree gives optimum results for all of the ''n''
|
|
listed above in the graph.
|
|
|
|
For ''n'' ≤ 100,000, the power tree method:
|
|
::* bests the factor method 88,803 times,
|
|
::* ties 11,191 times,
|
|
::* loses 6 times.
|
|
|
|
<br>
|
|
;References:
|
|
::* Donald E. Knuth's book: ''The Art of Computer Programming, Vol. 2'', Second Edition, Seminumerical Algorithms, section 4.6.3: Evaluation of Powers.
|
|
::* link [http://codegolf.stackexchange.com/questions/3177/knuths-power-tree codegolf.stackexchange.com/questions/3177/knuths-power-tree] It shows a '''Haskell''', '''Python''', and a '''Ruby''' computer program example (but they are mostly ''code golf'').
|
|
::* link [https://comeoncodeon.wordpress.com/tag/knuth/ comeoncodeon.wordpress.com/tag/knuth/] (See the section on Knuth's Power Tree.) It shows a '''C++''' computer program example.
|
|
::* link to Rosetta Code [http://rosettacode.org/wiki/Addition-chain_exponentiation addition-chain exponentiation].
|
|
<br><br>
|
|
|