Knuth's power tree: Difference between revisions

</pre>

=={{header|Phix}}==

{{trans|Go}}

<lang Phix>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 py = path(x)

for j=1 to length(py) do

integer y = x+py[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 bigatom.e

function treepow(object x, integer n)

-- x can be atom or bigatom

-- (asides: sequence r uses out-by-1 indexing, ie r[1] is for 0.

-- pipa/pa/res perform useful type-checking, ie prevent

-- this from trying to use something not yet calculated.)

sequence pn = path(n)

sequence r = {BA_ONE,ba_new(x)}&repeat(0,max(0,n-1))

integer p = 0

for i=1 to length(pn) do

integer pi = pn[i]

bigatom pipa = r[pi-p+1],

pa = r[p+1]

r[pi+1] = ba_mul(pipa,pa)

p = pi

end for

bigatom res = r[n+1]

return ba_sprint(res)

end function

procedure showpow(atom x, integer n)

printf(1,"%48s : %3g ^ %d = %s\n", {sprint(path(n)),x,n,treepow(x,n)})

end procedure

for n=0 to 17 do

showpow(2,n)

end for

showpow(1.1,81)

showpow(3,191)</lang>

{{out}}

<pre>

{} : 2 ^ 0 = 1

{1} : 2 ^ 1 = 2

{1,2} : 2 ^ 2 = 4

{1,2,3} : 2 ^ 3 = 8

{1,2,4} : 2 ^ 4 = 16

{1,2,4,5} : 2 ^ 5 = 32

{1,2,4,6} : 2 ^ 6 = 64

{1,2,4,6,7} : 2 ^ 7 = 128

{1,2,4,8} : 2 ^ 8 = 256

{1,2,4,8,9} : 2 ^ 9 = 512

{1,2,4,8,10} : 2 ^ 10 = 1024

{1,2,4,8,10,11} : 2 ^ 11 = 2048

{1,2,4,8,12} : 2 ^ 12 = 4096

{1,2,4,8,12,13} : 2 ^ 13 = 8192

{1,2,4,8,12,14} : 2 ^ 14 = 16384

{1,2,4,8,12,14,15} : 2 ^ 15 = 32768

{1,2,4,8,16} : 2 ^ 16 = 65536

{1,2,4,8,16,17} : 2 ^ 17 = 131072

{1,2,4,8,16,32,64,80,81} : 1.1 ^ 81 = 2253.24023604401248793730852872

{1,2,4,8,16,32,64,128,160,176,184,188,190,191} : 3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347