From 34dec8c16e5bb765cf4e920b0743e87ec90b77e8 Mon Sep 17 00:00:00 2001
From: Tavian Barnes <tavianator@gmail.com>
Date: Thu, 28 Oct 2010 15:58:55 -0400
Subject: Precalculate some binomial coefficients.

---
 libdimension/polynomial.c | 37 ++++++++++++++++++++++++++++---------
 1 file changed, 28 insertions(+), 9 deletions(-)

(limited to 'libdimension/polynomial.c')

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 */
-- 
cgit v1.2.3