user
(Knuth's power tree is used for computing   xn   efficiently.)

Task

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

:   :   * xn   for any real   x   and any non-negative integer   n.

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

:   :   * 2n     where   n   ranges from   0 ──► 17   (inclusive)
        * 3191
        * 1.181

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:

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

```

Where, for the power   43,   following the tree "downwards" from   1:

:   :   * (for   2)   compute square of   X,   store X2
        * (for   3)   compute   X \* X2,   store X3
        * (for   5)   compute   X3 \* X2,   store X5
        * (for 10)   compute square of   X5,   store X10
        * (for 20)   compute square of   X10,   store X20
        * (for 40)   compute square of   X20,   store X40
        * (for 43)   compute   X40 \* X3   (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   X   (which was previously calculated).
  For the last multiplication in the above example, it would be   (43-40),   or   3.

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.

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   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   comeoncodeon.wordpress.com/tag/knuth/     (See the section on Knuth's Power Tree.)     It shows a   **C++**   computer program example.
        * link to Rosetta Code   addition-chain exponentiation.
assistant
(formerly Perl 6)
Paths are random. It is possible replace `.pick(*)` with `.reverse` if you want paths as in Perl, or remove it for Python paths.

```
use v6;

sub power-path ($n ) {
    state @unused_nodes = (2,);
    state @power-tree = (False,0,1);
    
    until @power-tree[$n].defined {
        my $node = @unused_nodes.shift;

        for  $node X+ power-path($node).pick(*) {
            next if @power-tree[$_].defined;
            @unused_nodes.push($_);
            @power-tree[$_]= $node;
        }        
    }

    ( $n, { @power-tree[$_] } ...^ 0 ).reverse;
}

multi power ( $, 0 ) { 1 };
multi power ( $n, $exponent ) {
    state  %p;
    my     %r =  %p{$n}  // ( 0 => 1, 1 => $n ) ;  

    for power-path( $exponent ).rotor( 2 => -1 ) -> ( $p, $c ) {
        %r{ $c } = %r{ $p } * %r{ $c - $p }
    }

    %p{$n} := %r ;
    %r{ $exponent }
}

say 'Power paths: ',      pairs map *.&power-path,    ^18;
say '2 ** key = value: ', pairs map { 2.&power($_) }, ^18; 

say 'Path for 191: ', power-path 191;
say '3 ** 191 = ',    power   3, 191;
say 'Path for 81: ',  power-path  81;
say '1.1 ** 81 = ',   power 1.1,  81;

```

Output:

```
Power paths: (0 => () 1 => (1) 2 => (1 2) 3 => (1 2 3) 4 => (1 2 4) 5 => (1 2 3 5) 6 => (1 2 3 6) 7 => (1 2 3 6 7) 8 => (1 2 4 8) 9 => (1 2 3 6 9) 10 => (1 2 3 5 10) 11 => (1 2 3 6 9 11) 12 => (1 2 3 6 12) 13 => (1 2 3 6 12 13) 14 => (1 2 3 6 12 14) 15 => (1 2 3 6 9 15) 16 => (1 2 4 8 16) 17 => (1 2 4 8 16 17))
2 ** key = value: (0 => 1 1 => 2 2 => 4 3 => 8 4 => 16 5 => 32 6 => 64 7 => 128 8 => 256 9 => 512 10 => 1024 11 => 2048 12 => 4096 13 => 8192 14 => 16384 15 => 32768 16 => 65536 17 => 131072)
Path for 191: (1 2 3 6 9 18 27 54 108 162 189 191)
3 ** 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
Path for 81: (1 2 3 6 9 18 27 54 81)
1.1 ** 81 = 2253.24023604401

```