(Knuth's power tree is used for computing &nbsp; <big><big>x<sup>n</sup></big></big> &nbsp; efficiently.)<br>


;Task:
Compute and show the list of Knuth's power tree integers necessary for the computation of:

::* &nbsp; <big><big>x<sup>n</sup></big></big> &nbsp; for any real &nbsp; <big><big>x</big></big> &nbsp; and any non-negative integer &nbsp; <big>n</big>.



Then, using those integers, calculate and show the exact values of (at least) the integer powers below:

::* &nbsp; <big>2<sup>n</sup></big> &nbsp; &nbsp; where &nbsp; n &nbsp; ranges from &nbsp; 0 ──► 17 &nbsp; (inclusive) <br>
::* &nbsp; <big>3<sup>191</sup></big>
::* &nbsp; <big>1.1<sup>81</sup></big>


A &nbsp;''zero''&nbsp; 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 &nbsp; <big>43</big>, &nbsp; following the tree "downwards" from &nbsp; <big>1</big>:
::* &nbsp; (for &nbsp; 2) &nbsp; compute square of &nbsp; <big>X</big>, &nbsp; store <big>X<sup>2</sup></big>
::* &nbsp; (for &nbsp; 3) &nbsp; compute &nbsp; <big>X</big> * <big>X<sup>2</sup></big>, &nbsp; store <big>X<sup>3</sup></big>
::* &nbsp; (for &nbsp; 5) &nbsp; compute &nbsp; <big>X<sup>3</sup></big> * <big>X<sup>2</sup></big>, &nbsp; store <big>X<sup>5</sup></big>
::* &nbsp; (for 10) &nbsp; compute square of &nbsp; <big>X<sup>5</sup></big>, &nbsp; store <big>X<sup>10</sup></big>
::* &nbsp; (for 20) &nbsp; compute square of &nbsp; <big>X<sup>10</sup></big>, &nbsp; store <big>X<sup>20</sup></big>
::* &nbsp; (for 40) &nbsp; compute square of &nbsp; <big>X<sup>20</sup></big>, &nbsp; store <big>X<sup>40</sup></big>
::* &nbsp; (for 43) &nbsp; compute &nbsp; <big>X<sup>40</sup></big> * <big>X<sup>3</sup></big> &nbsp; (result).

Note that for every even integer (in the power tree), &nbsp; one just squares the previous value.

For an odd integer, multiply the previous value with an appropriate odd power of &nbsp; <big>X</big> &nbsp; (which was previously calculated).
&nbsp; For the last multiplication in the above example, it would be &nbsp; <big>(43-40)</big>, &nbsp; or &nbsp; <big>3</big>. <br>

According to Dr. Knuth (see below), &nbsp; computer tests have shown that this power tree gives optimum results for all of the &nbsp; ''n''
&nbsp; listed above in the graph. 

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.

<br>
;References:
::* &nbsp; Donald E. Knuth's book: &nbsp; ''The Art of Computer Programming, Vol. 2'', Second Edition, Seminumerical Algorithms, section 4.6.3: Evaluation of Powers.
::* &nbsp; link &nbsp; [http://codegolf.stackexchange.com/questions/3177/knuths-power-tree codegolf.stackexchange.com/questions/3177/knuths-power-tree] &nbsp; &nbsp; It shows a &nbsp; '''Haskell''', &nbsp; '''Python''', &nbsp; and a &nbsp; '''Ruby''' &nbsp; computer program example &nbsp; (but they are mostly &nbsp; ''code golf'').
::* &nbsp; link &nbsp; [https://comeoncodeon.wordpress.com/tag/knuth/ comeoncodeon.wordpress.com/tag/knuth/] &nbsp; &nbsp; (See the section on Knuth's Power Tree.) &nbsp; &nbsp; It shows a &nbsp; '''C++''' &nbsp; computer program example.
::* &nbsp; link to Rosetta Code &nbsp; [http://rosettacode.org/wiki/Addition-chain_exponentiation addition-chain exponentiation].
<br><br>

