math/big: faster Int.Binomial(n, k) for k > n/2
benchmark old ns/op new ns/op delta
BenchmarkBinomial 478664 4410 -99.08%
Fixes #10084.
Change-Id: Ib75034428e32c79c9a660ae9f9bd396afc6a7f11
Reviewed-on: https://go-review.googlesource.com/8351
Reviewed-by: Alan Donovan <adonovan@google.com>
diff --git a/src/math/big/int_test.go b/src/math/big/int_test.go
index 058dd96..a972a72 100644
--- a/src/math/big/int_test.go
+++ b/src/math/big/int_test.go
@@ -219,6 +219,45 @@
}
}
+func TestBinomial(t *testing.T) {
+ var z Int
+ for _, test := range []struct {
+ n, k int64
+ want string
+ }{
+ {0, 0, "1"},
+ {0, 1, "0"},
+ {1, 0, "1"},
+ {1, 1, "1"},
+ {1, 10, "0"},
+ {4, 0, "1"},
+ {4, 1, "4"},
+ {4, 2, "6"},
+ {4, 3, "4"},
+ {4, 4, "1"},
+ {10, 1, "10"},
+ {10, 9, "10"},
+ {10, 5, "252"},
+ {11, 5, "462"},
+ {11, 6, "462"},
+ {100, 10, "17310309456440"},
+ {100, 90, "17310309456440"},
+ {1000, 10, "263409560461970212832400"},
+ {1000, 990, "263409560461970212832400"},
+ } {
+ if got := z.Binomial(test.n, test.k).String(); got != test.want {
+ t.Errorf("Binomial(%d, %d) = %s; want %s", test.n, test.k, got, test.want)
+ }
+ }
+}
+
+func BenchmarkBinomial(b *testing.B) {
+ var z Int
+ for i := b.N - 1; i >= 0; i-- {
+ z.Binomial(1000, 990)
+ }
+}
+
// Examples from the Go Language Spec, section "Arithmetic operators"
var divisionSignsTests = []struct {
x, y int64
