← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to test/garbage/peano.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
test/garbage/peano.go
 
1
// $G $F.go && $L $F.$A && ./$A.out
 
2
 
 
3
// Copyright 2009 The Go Authors. All rights reserved.
 
4
// Use of this source code is governed by a BSD-style
 
5
// license that can be found in the LICENSE file.
 
6
 
 
7
package main
 
8
 
 
9
import (
 
10
        "fmt"
 
11
        "runtime"
 
12
        "time"
 
13
)
 
14
 
 
15
 
 
16
type Number struct {
 
17
        next *Number
 
18
}
 
19
 
 
20
 
 
21
// -------------------------------------
 
22
// Peano primitives
 
23
 
 
24
func zero() *Number { return nil }
 
25
 
 
26
 
 
27
func is_zero(x *Number) bool { return x == nil }
 
28
 
 
29
 
 
30
func add1(x *Number) *Number {
 
31
        e := new(Number)
 
32
        e.next = x
 
33
        return e
 
34
}
 
35
 
 
36
 
 
37
func sub1(x *Number) *Number { return x.next }
 
38
 
 
39
 
 
40
func add(x, y *Number) *Number {
 
41
        if is_zero(y) {
 
42
                return x
 
43
        }
 
44
 
 
45
        return add(add1(x), sub1(y))
 
46
}
 
47
 
 
48
 
 
49
func mul(x, y *Number) *Number {
 
50
        if is_zero(x) || is_zero(y) {
 
51
                return zero()
 
52
        }
 
53
 
 
54
        return add(mul(x, sub1(y)), x)
 
55
}
 
56
 
 
57
 
 
58
func fact(n *Number) *Number {
 
59
        if is_zero(n) {
 
60
                return add1(zero())
 
61
        }
 
62
 
 
63
        return mul(fact(sub1(n)), n)
 
64
}
 
65
 
 
66
 
 
67
// -------------------------------------
 
68
// Helpers to generate/count Peano integers
 
69
 
 
70
func gen(n int) *Number {
 
71
        if n > 0 {
 
72
                return add1(gen(n - 1))
 
73
        }
 
74
 
 
75
        return zero()
 
76
}
 
77
 
 
78
 
 
79
func count(x *Number) int {
 
80
        if is_zero(x) {
 
81
                return 0
 
82
        }
 
83
 
 
84
        return count(sub1(x)) + 1
 
85
}
 
86
 
 
87
 
 
88
func check(x *Number, expected int) {
 
89
        var c = count(x)
 
90
        if c != expected {
 
91
                panic(fmt.Sprintf("error: found %d; expected %d", c, expected))
 
92
        }
 
93
}
 
94
 
 
95
 
 
96
// -------------------------------------
 
97
// Test basic functionality
 
98
 
 
99
func verify() {
 
100
        check(zero(), 0)
 
101
        check(add1(zero()), 1)
 
102
        check(gen(10), 10)
 
103
 
 
104
        check(add(gen(3), zero()), 3)
 
105
        check(add(zero(), gen(4)), 4)
 
106
        check(add(gen(3), gen(4)), 7)
 
107
 
 
108
        check(mul(zero(), zero()), 0)
 
109
        check(mul(gen(3), zero()), 0)
 
110
        check(mul(zero(), gen(4)), 0)
 
111
        check(mul(gen(3), add1(zero())), 3)
 
112
        check(mul(add1(zero()), gen(4)), 4)
 
113
        check(mul(gen(3), gen(4)), 12)
 
114
 
 
115
        check(fact(zero()), 1)
 
116
        check(fact(add1(zero())), 1)
 
117
        check(fact(gen(5)), 120)
 
118
}
 
119
 
 
120
 
 
121
// -------------------------------------
 
122
// Factorial
 
123
 
 
124
 
 
125
func main() {
 
126
        t0 := time.Nanoseconds()
 
127
        verify()
 
128
        for i := 0; i <= 9; i++ {
 
129
                print(i, "! = ", count(fact(gen(i))), "\n")
 
130
        }
 
131
        runtime.GC()
 
132
        t1 := time.Nanoseconds()
 
133
 
 
134
        gcstats("BenchmarkPeano", 1, t1-t0)
 
135
}