diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 13:18:25 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 13:18:25 +0000 |
commit | 109be507377fe7f6e8819ac94041d3fdcdf6fd2f (patch) | |
tree | 2806a689f8fab4a2ec9fc949830ef270a91d667d /test/bench/garbage/peano.go | |
parent | Initial commit. (diff) | |
download | golang-1.19-109be507377fe7f6e8819ac94041d3fdcdf6fd2f.tar.xz golang-1.19-109be507377fe7f6e8819ac94041d3fdcdf6fd2f.zip |
Adding upstream version 1.19.8.upstream/1.19.8upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'test/bench/garbage/peano.go')
-rw-r--r-- | test/bench/garbage/peano.go | 121 |
1 files changed, 121 insertions, 0 deletions
diff --git a/test/bench/garbage/peano.go b/test/bench/garbage/peano.go new file mode 100644 index 0000000..6c7e523 --- /dev/null +++ b/test/bench/garbage/peano.go @@ -0,0 +1,121 @@ +// run + +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package main + +import ( + "fmt" + "runtime" + "time" +) + +type Number struct { + next *Number +} + +// ------------------------------------- +// Peano primitives + +func zero() *Number { return nil } + +func is_zero(x *Number) bool { return x == nil } + +func add1(x *Number) *Number { + e := new(Number) + e.next = x + return e +} + +func sub1(x *Number) *Number { return x.next } + +func add(x, y *Number) *Number { + if is_zero(y) { + return x + } + + return add(add1(x), sub1(y)) +} + +func mul(x, y *Number) *Number { + if is_zero(x) || is_zero(y) { + return zero() + } + + return add(mul(x, sub1(y)), x) +} + +func fact(n *Number) *Number { + if is_zero(n) { + return add1(zero()) + } + + return mul(fact(sub1(n)), n) +} + +// ------------------------------------- +// Helpers to generate/count Peano integers + +func gen(n int) *Number { + if n > 0 { + return add1(gen(n - 1)) + } + + return zero() +} + +func count(x *Number) int { + if is_zero(x) { + return 0 + } + + return count(sub1(x)) + 1 +} + +func check(x *Number, expected int) { + var c = count(x) + if c != expected { + panic(fmt.Sprintf("error: found %d; expected %d", c, expected)) + } +} + +// ------------------------------------- +// Test basic functionality + +func verify() { + check(zero(), 0) + check(add1(zero()), 1) + check(gen(10), 10) + + check(add(gen(3), zero()), 3) + check(add(zero(), gen(4)), 4) + check(add(gen(3), gen(4)), 7) + + check(mul(zero(), zero()), 0) + check(mul(gen(3), zero()), 0) + check(mul(zero(), gen(4)), 0) + check(mul(gen(3), add1(zero())), 3) + check(mul(add1(zero()), gen(4)), 4) + check(mul(gen(3), gen(4)), 12) + + check(fact(zero()), 1) + check(fact(add1(zero())), 1) + check(fact(gen(5)), 120) +} + +// ------------------------------------- +// Factorial + +func main() { + t0 := time.Now() + verify() + for i := 0; i <= 9; i++ { + print(i, "! = ", count(fact(gen(i))), "\n") + } + runtime.GC() + t1 := time.Now() + + gcstats("BenchmarkPeano", 1, t1.Sub(t0)) +} |