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


with javascript_semantics
constant p = new_dict({{1,0}})
sequence lvl = {1}
 
function path(integer n)
    if n=0 then return {} end if
    while getd_index(n,p)=NULL do
        sequence q = {}
        for i=1 to length(lvl) do
            integer x = lvl[i]
            sequence px = path(x)
            for j=1 to length(px) do
                integer y = x+px[j]
                if getd_index(y,p)!=NULL then exit end if
                setd(y,x,p)
                q &= y
            end for
        end for
        lvl = q
    end while
    return path(getd(n,p))&n
end function
 
include mpfr.e
mpfr_set_default_precision(500)
 
function treepow(object x, integer n, sequence pn = {})
-- x can be atom or string (but not mpfr)
-- (asides: sequence r uses out-by-1 indexing, ie r[1] is for 0.
--          sequence c is used to double-check we are not trying
--          to use something which has not yet been calculated.)
    if pn={} then pn=path(n) end if
    sequence r = {mpfr_init(1),mpfr_init(x)},
             c = {1,1}&repeat(0,max(0,n-1))
    for i=1 to max(0,n-1) do r &= mpfr_init() end for
    integer p = 0
    for i=1 to length(pn) do
        integer pi = pn[i]
        if c[pi-p+1]=0 then ?9/0 end if
        if c[p+1]=0 then ?9/0 end if
        mpfr_mul(r[pi+1],r[pi-p+1],r[p+1])
        c[pi+1] = 1
        p = pi
    end for
--  string res = shorten(trim_tail(mpfr_sprintf("%.83Rf",r[n+1]),".0"))
    string res = shorten(trim_tail(mpfr_get_fixed(r[n+1],83),".0"))
    r = mpfr_free(r)
    return res
end function
 
procedure showpow(object x, integer n)
    sequence pn = path(n)
    string xs = iff(string(x)?x:sprintf("%3g",x))
    printf(1,"%48v : %3s ^ %d = %s\n", {pn,xs,n,treepow(x,n,pn)})
end procedure
 
for n=0 to 17 do
    showpow(2,n)
end for
showpow("1.1",81)
showpow(3,191)
