Knuth's power tree: Difference between revisions
Added Go
(Added Julia language) |
(Added Go) |
||
Line 193:
(power-exp 3 #( 1 2 3 5 7 14 19 38 57 95 190 191) )
→ 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
</pre>
=={{header|Go}}==
{{trans|Kotlin}}
<lang go>package main
import (
"fmt"
"math/big"
)
var (
p = map[int]int{1: 0}
lvl = [][]int{[]int{1}}
)
func path(n int) []int {
if n == 0 {
return []int{}
}
for {
if _, ok := p[n]; ok {
break
}
var q []int
for _, x := range lvl[0] {
for _, y := range path(x) {
z := x + y
if _, ok := p[z]; ok {
break
}
p[z] = x
q = append(q, z)
}
}
lvl[0] = q
}
r := path(p[n])
r = append(r, n)
return r
}
func treePow(x float64, n int) *big.Float {
r := map[int]*big.Float{0: big.NewFloat(1), 1: big.NewFloat(x)}
p := 0
for _, i := range path(n) {
temp := new(big.Float).SetPrec(320)
temp.Mul(r[i-p], r[p])
r[i] = temp
p = i
}
return r[n]
}
func showPow(x float64, n int, isIntegral bool) {
fmt.Printf("%d: %v\n", n, path(n))
f := "%f"
if isIntegral {
f = "%.0f"
}
fmt.Printf(f, x)
fmt.Printf(" ^ %d = ", n)
fmt.Printf(f+"\n\n", treePow(x, n))
}
func main() {
for n := 0; n <= 17; n++ {
showPow(2, n, true)
}
showPow(1.1, 81, false)
showPow(3, 191, true)
}</lang>
{{out}}
<pre>
0: []
2 ^ 0 = 1
1: [1]
2 ^ 1 = 2
2: [1 2]
2 ^ 2 = 4
3: [1 2 3]
2 ^ 3 = 8
4: [1 2 4]
2 ^ 4 = 16
5: [1 2 4 5]
2 ^ 5 = 32
6: [1 2 4 6]
2 ^ 6 = 64
7: [1 2 4 6 7]
2 ^ 7 = 128
8: [1 2 4 8]
2 ^ 8 = 256
9: [1 2 4 8 9]
2 ^ 9 = 512
10: [1 2 4 8 10]
2 ^ 10 = 1024
11: [1 2 4 8 10 11]
2 ^ 11 = 2048
12: [1 2 4 8 12]
2 ^ 12 = 4096
13: [1 2 4 8 12 13]
2 ^ 13 = 8192
14: [1 2 4 8 12 14]
2 ^ 14 = 16384
15: [1 2 4 8 12 14 15]
2 ^ 15 = 32768
16: [1 2 4 8 16]
2 ^ 16 = 65536
17: [1 2 4 8 16 17]
2 ^ 17 = 131072
81: [1 2 4 8 16 32 64 80 81]
1.100000 ^ 81 = 2253.240236
191: [1 2 4 8 16 32 64 128 160 176 184 188 190 191]
3 ^ 191 = 13494588674281093803728157396523884917402502294030101914066705367021922008906273586058258347
</pre>
| |||