(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.


/*REXX program produces & displays a  power tree  for P,  and calculates & displays X^P.*/
numeric digits 1000                              /*be able to handle some large numbers.*/
parse arg XP                                     /*get sets:   X, low power, high power.*/
if XP=''  then XP='2 -4 17   3 191 191   1.1 81' /*Not specified?  Then use the default.*/
          /*────── X LP HP   X  LP  HP    X  LP  ◄── X, low power, high power ··· repeat*/
     do  until XP=''
     parse var XP    x pL pH   XP;    x= x / 1   /*get X, lowP, highP; and normalize X. */
     if pH=''  then pH= pL                       /*No highPower?  Then assume lowPower. */
 
       do e=pL  to pH;           p= abs(e) / 1   /*use a range of powers;   use  │E│    */
       $= powerTree(p);          w= length(pH)   /*construct the power tree, (pow list).*/
                                                 /* [↑]  W≡length for an aligned display*/
          do i=1  for words($);  @.i= word($, i) /*build a fast Knuth's power tree array*/
          end   /*i*/
 
       if p==0  then do;  z= 1;  call show;  iterate;  end  /*handle case of zero power.*/
       !.= .;   z= x;     !.1= z;     prv= z     /*define/construct the first power of X*/
 
           do k=2  to words($);       n= @.k     /*obtain the power (number) to be used.*/
           prev= k - 1;     diff= n - @.prev     /*these are used for the odd powers.   */
           if n//2==0  then z= prv ** 2          /*Even power?   Then square the number.*/
                       else z= z * !.diff        /* Odd   "        "  mult. by pow diff.*/
           !.n= z                                /*remember for other multiplications.  */
           prv= z                                /*remember for squaring the numbers.   */
           end   /*k*/
       call show                                 /*display the expression and its value.*/
       end       /*e*/
     end         /*until XP ···*/
exit 0                                           /*stick a fork in it,  we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
powerTree: arg y 1 oy;   $=                      /*Z is the result; $ is the power tree.*/
           if y=0 | y=1  then return y           /*handle special cases for zero & unity*/
           #.= 0;   @.= 0;    #.0= 1             /*define default & initial array values*/
                                                 /* [↓]  add blank "flag" thingy──►list.*/
                   do  while \(y//2);  $= $ ' '  /*reduce "front" even power #s to odd #*/
                   if y\==oy  then $= y $        /*(only)  ignore the first power number*/
                   y= y % 2                      /*integer divide the power (it's even).*/
                   end   /*while*/
 
           if $\==''  then $= y $                /*re─introduce the last power number.  */
           $= $ oy                               /*insert last power number 1st in list.*/
           if y>1  then do      while  @.y==0;            n= #.0;        m= 0
                          do    while  n\==0;             q= 0;          s= n
                            do  while  s\==0;             _= n + s
                            if @._==0  then do;  if q==0  then m_= _;
                                                 #._= q;  @._= n;        q= _
                                            end
                            s= @.s
                            end   /*while s¬==0*/
                          if q\==0  then do;   #.m= q;   m= m_;   end
                          n= #.n
                          end     /*while n¬==0*/
                        #.m= 0
                        end       /*while @.y==0*/
           z= @.y
                            do  while z\==0;   $= z $;   z= @.z;  end /*build power list*/
           return space($)                                            /*del extra blanks*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: if e<0  then z=format(1/z, , 40)/1;     _=right(e, w)           /*use reciprocal? */
      say left('power tree for '  _  " is: "  $,60)  '═══'  x"^"_  ' is: '  z;      return