avgtest.go

package main

// https://www.reddit.com/r/coding/comments/3vsw5o/gettin_arithmetic_mean_right/

import "fmt"
import "math/big"
import "math/rand"

func naiveMean(rnd *rand.Rand, n int) float64 {
	sum := 0.0

	for i := 0; i < n; i++ {
		sum += rnd.NormFloat64()
	}

	return sum / float64(n)
}

func kahanMean(rnd *rand.Rand, n int) float64 {
	sum := 0.0
	c := 0.0

	for i := 0; i < n; i++ {
		y := rnd.NormFloat64() - c
		t := sum + y
		c = (t - sum) - y
		sum = t
	}

	return sum / float64(n)
}

func predivMean(rnd *rand.Rand, n int) float64 {
	sum := 0.0

	for i := 0; i < n; i++ {
		sum += rnd.NormFloat64() / float64(n)
	}

	return sum
}

func predivKahanMean(rnd *rand.Rand, n int) float64 {
	sum := 0.0
	c := 0.0

	for i := 0; i < n; i++ {
		y := rnd.NormFloat64()/float64(n) - c
		t := sum + y
		c = (t - sum) - y
		sum = t
	}

	return sum
}

func runningMean(rnd *rand.Rand, n int) float64 {
	sum := 0.0

	for i := 0; i < n; i++ {
		sum += (rnd.NormFloat64() - sum) / float64(i+1)
	}

	return sum
}

func exactMean(rnd *rand.Rand, n int) float64 {
	var sum, k big.Rat

	for i := 0; i < n; i++ {
		k.SetFloat64(rnd.NormFloat64())
		sum.Add(&sum, &k)
	}

	k.SetInt64(int64(n))
	sum.Quo(&sum, &k)

	result, _ := sum.Float64()

	return result
}

var funcs = []struct {
	name     string
	meanfunc func(*rand.Rand, int) float64
}{
	{"naive", naiveMean},
	{"kahan", kahanMean},
	{"prediv", predivMean},
	{"predivKahan", predivKahanMean},
	{"running", runningMean},
	{"exact", exactMean},
}

func main() {
	var seed int64 = 1337
	n := 1000000000

	for _, fn := range funcs {
		fmt.Printf("%12s: %.15e\n", fn.name, fn.meanfunc(rand.New(rand.NewSource(seed)), n))
	}
}