summaryrefslogtreecommitdiffstats
path: root/libdimension
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@gmail.com>2010-10-28 15:58:55 -0400
committerTavian Barnes <tavianator@gmail.com>2010-10-28 15:58:55 -0400
commit34dec8c16e5bb765cf4e920b0743e87ec90b77e8 (patch)
tree1fbc5032d2fa871adff2509ca2d6157f361d608e /libdimension
parent8d8d44434bb876b8bf77ce2e77c2946cff0432c7 (diff)
downloaddimension-34dec8c16e5bb765cf4e920b0743e87ec90b77e8.tar.xz
Precalculate some binomial coefficients.
Diffstat (limited to 'libdimension')
-rw-r--r--libdimension/polynomial.c37
1 files changed, 28 insertions, 9 deletions
diff --git a/libdimension/polynomial.c b/libdimension/polynomial.c
index d78361c..77e561d 100644
--- a/libdimension/polynomial.c
+++ b/libdimension/polynomial.c
@@ -148,21 +148,40 @@ dmnsn_descartes_rule(double poly[], size_t degree)
return changes;
}
+#define DMNSN_NBINOM 11
+static const double dmnsn_pascals_triangle[DMNSN_NBINOM][DMNSN_NBINOM] = {
+ { 1.0 },
+ { 1.0, 1.0 },
+ { 1.0, 2.0, 1.0 },
+ { 1.0, 3.0, 3.0, 1.0 },
+ { 1.0, 4.0, 6.0, 4.0, 1.0 },
+ { 1.0, 5.0, 10.0, 10.0, 5.0, 1.0 },
+ { 1.0, 6.0, 15.0, 20.0, 15.0, 6.0, 1.0 },
+ { 1.0, 7.0, 21.0, 35.0, 35.0, 21.0, 7.0, 1.0 },
+ { 1.0, 8.0, 28.0, 56.0, 70.0, 56.0, 28.0, 8.0, 1.0 },
+ { 1.0, 9.0, 36.0, 84.0, 126.0, 126.0, 84.0, 36.0, 9.0, 1.0 },
+ { 1.0, 10.0, 45.0, 120.0, 210.0, 252.0, 210.0, 120.0, 45.0, 10.0, 1.0 }
+};
+
/* Get the (n k) binomial coefficient */
static inline double
dmnsn_binom(size_t n, size_t k)
{
- if (k > n - k) {
- k = n - k;
- }
+ if (n < DMNSN_NBINOM && k < DMNSN_NBINOM) {
+ return dmnsn_pascals_triangle[n][k];
+ } else {
+ if (k > n - k) {
+ k = n - k;
+ }
- double ret = 1.0;
- for (size_t i = 0; i < k; ++i) {
- ret *= n - i;
- ret /= i + 1;
- }
+ double ret = 1.0;
+ for (size_t i = 0; i < k; ++i) {
+ ret *= n - i;
+ ret /= i + 1;
+ }
- return ret;
+ return ret;
+ }
}
/* Find all ranges that contain a single root, with Uspensky's algorithm */