Ackermann function: Difference between revisions
Content added Content deleted
(→{{header|Go}}: add sub-sections; remove unsafe usage; recover from panic; add A(3,1e6) and A(4,2)) |
|||
Line 2,738:
=={{header|Go}}==
===Classic version===
<lang go>func Ackermann(m, n uint) uint {
switch 0 {
Line 2,748:
return Ackermann(m - 1, Ackermann(m, n - 1))
}</lang>
===Expanded version===
<lang go>func Ackermann2(m, n uint) uint {
switch {
Line 2,764:
return Ackermann2(m - 1, Ackermann2(m, n - 1))
}</lang>
===Expanded version with arbitrary precision
<lang go>package main
import (
"math/bits" // Added in Go 1.9
)
Line 2,777:
var three = big.NewInt(3)
var eight = big.NewInt(8)
func Ackermann2(m, n *big.Int) *big.Int {
if nb
// n is too large to represent as a
// uint for use in the Lsh method.
panic(TooBigError(nb))
r := new(big.Int).Lsh(eight, uint(n.Int64()))▼
return r.Sub(r, three)▼
// If we tried to continue anyway, doing
// 8*2^n-3 as bellow, we'd use hundreds
// of megabytes and lots of CPU time
if n.BitLen() == 0 {▼
// without the Exp call even returning.
return Ackermann2(new(big.Int).Sub(m, one), one)▼
r := new(big.Int).Exp(two, n, nil)
r.Mul(eight, r)
return Ackermann2(new(big.Int).Sub(m, one),▼
Ackermann2(m, new(big.Int).Sub(n, one)))▼
}
return r.Sub(r, three)
}
}
}
}
type TooBigError int
func (e TooBigError) Error() string {
return fmt.Sprintf("A(m,n) had n of %d bits; too large", int(e))
}
func main() {
show(4, 2)
show(4, 3)
}
func show(m, n int64) {
defer func() {
fmt.Printf("A(%d, %d) = ", m, n)▼
// Ackermann2 could/should have returned an error
fmt.Println(Ackermann2(big.NewInt(m), big.NewInt(n)))▼
// instead of a panic. But here's how to recover
// from the panic, and report "expected" errors.
if e := recover(); e != nil {
if err, ok := e.(TooBigError); ok {
fmt.Println("Error:", err)
} else {
panic(e)
}
}
}()
if a.BitLen() <= 256 {
fmt.Println(a)
} else {
s := a.String()
fmt.Printf("%d digits starting/ending with: %s...%s\n",
len(s), s[:20], s[len(s)-20:],
)
}
}</lang>
{{out}}
Line 2,824 ⟶ 2,861:
A(2, 4) = 11
A(3, 100) = 10141204801825835211973625643005
A(3, 1000000) = 301031 digits starting/ending with: 79205249834367186005...39107225301976875005
A(4, 1) = 65533
A(4, 2) = 19729 digits starting/ending with: 20035299304068464649...45587895905719156733
A(4, 3) = Error: A(m,n) had n of 65536 bits; too large
</pre>
| |||