math/big: Binomial can be be twice as fast on average by using symetry #10084
Description
The current implementation of Binomial(n, k int64) *Int performs 2*k big.nat multiplications. This can be much improved for any k>n/2, since math gives us Binomial(n,k) == Binomial(n,n-k).
This is trivial to implement and gives on average an substantive improvement both in CPU and memory consumption.
On a shiny Intel Core i7 processor:
$ go test -bench=.
PASS
BenchmarkStd-2 500 2889379 ns/op
BenchmarkFancy-2 1000 1384765 ns/op
ok _/home/intel 3.289s
[go version devel +122384e 2015-03-04 20:55:55 +0000 linux/amd64]
On a raspberry pi 1 Model B rev. 2:
$ go test -bench=.
PASS
BenchmarkStd 20 74138648 ns/op
BenchmarkFancy 50 37191099 ns/op
ok _/home/pi 3.744s
[go version devel +5432b4d Sun Mar 1 18:38:21 2015 +0000 linux/arm]
/* save the following as binomial_test.go */
package main
import (
"math/big"
"testing"
)
type binomialFunc func(n, k int) *big.Int
// nearly the same as big.Binomial
func stdBinomial(n, k int) *big.Int {
var res big.Int
return res.Binomial(int64(n), int64(k))
}
// a improved function which takes advantage of symetry
func fancyBinomial(n, k int) *big.Int {
if k > n/2 {
return stdBinomial(n, n-k)
}
return stdBinomial(n, k)
}
func proofEquality(t *testing.T, f, g binomialFunc, n int) {
for k := 0; k <= n; k++ {
a := f(n, k)
b := g(n, k)
if a.Cmp(b) != 0 {
t.Errorf("binom(%d, %d) = %s ≠ %s\n", n, k, a, b)
}
}
}
// Test if the improved function calculates the same values as the old one
func TestEquality(t *testing.T) {
proofEquality(t, stdBinomial, fancyBinomial, 100) // 100 == ∞ ;)
}
// Calculates all values of binomial(n,k) for a given n and test if the symetry holds
func doSymmetry(b *testing.B, binom binomialFunc, n int) {
upto := n / 2
for k := 0; k < upto; k++ {
l := binom(n, k)
u := binom(n, n-k)
if l.Cmp(u) != 0 {
b.Fatalf("binom(%d, %d) = %s ≠ %s = binom(%d, %d)\n", n, k, l, u, n, n-k)
}
}
if (n % 2) == 0 {
binom(n, upto+1) // a lonely ›true‹ middle point is only symetric to itself
}
}
func BenchmarkStd(t *testing.B) {
for i := 0; i < t.N; i++ {
doSymmetry(t, stdBinomial, 100)
}
}
func BenchmarkFancy(t *testing.B) {
for i := 0; i < t.N; i++ {
doSymmetry(t, fancyBinomial, 100)
}
}