...
Run Format

Source file test/bench/garbage/peano.go

Documentation: test/bench/garbage

  // 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))
  }
  

View as plain text