Anonymous user
Knuth's power tree: Difference between revisions
→{{header|REXX}}: Added zkl
(Add Racket) |
(→{{header|REXX}}: Added zkl) |
||
Line 446:
power tree for 191 is: 1 2 3 5 7 14 19 38 57 95 190 191 ═══ 3^191 is: 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
power tree for 81 is: 1 2 3 5 10 20 40 41 81 ═══ 1.1^81 is: 2253.240236044012487937308538033349567966729852481170503814810577345406584190098644811
</pre>
=={{header|zkl}}==
{{trans|Python}}
<lang zkl># remember the tree generation state and expand on demand
fcn path(n,p=Dictionary(1,0),lvl=List(List(1))){
if(n==0) return(T);
while(not p.holds(n)){
q:=List();
foreach x,y in (lvl[0],path(x,p,lvl)){
if(p.holds(x+y)) break; // not this y
y=x+y; p[y]=x;
q.append(y);
}
lvl[0]=q
}
path(p[n],p,lvl) + n
}
fcn tree_pow(x,n,path){
r,p:=D(0,1, 1,x), 0;
foreach i in (path){ r[i]=r[i-p]*r[p]; p=i; }
r[n]
}
fcn show_pow(x,n){
fmt:="%d: %s\n" + T("%g^%d = %f", "%d^%d = %d")[x==Int(x)] + "\n";
println(fmt.fmt(n,p:=path(n),x,n,tree_pow(x,n,p)))
}</lang>
<lang zkl>foreach x in (18){ show_pow(2,x) }
show_pow(1.1,81);
var [const] BN=Import("zklBigNum"); // GNU GMP big ints
show_pow(BN(3),191);</lang>
{{out}}
<pre style="height:32ex;overflow:scroll">
0: L()
2^0 = 1
1: L(1)
2^1 = 2
2: L(1,2)
2^2 = 4
3: L(1,2,3)
2^3 = 8
4: L(1,2,4)
2^4 = 16
5: L(1,2,4,5)
2^5 = 32
6: L(1,2,4,6)
2^6 = 64
7: L(1,2,4,6,7)
2^7 = 128
8: L(1,2,4,8)
2^8 = 256
9: L(1,2,4,8,9)
2^9 = 512
10: L(1,2,4,8,10)
2^10 = 1024
11: L(1,2,4,8,10,11)
2^11 = 2048
12: L(1,2,4,8,12)
2^12 = 4096
13: L(1,2,4,8,12,13)
2^13 = 8192
14: L(1,2,4,8,12,14)
2^14 = 16384
15: L(1,2,4,8,12,14,15)
2^15 = 32768
16: L(1,2,4,8,16)
2^16 = 65536
17: L(1,2,4,8,16,17)
2^17 = 131072
81: L(1,2,4,8,16,32,64,80,81)
1.1^81 = 2253.240236
191: L(1,2,4,8,16,32,64,128,160,176,184,188,190,191)
3^191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
</pre>
| |||