[alexandria.git] updated branch master: e6d5005 optimizations to BINOMIAL-COEFFICIENT and COUNT-PERMUATIONS

[Nikodemus Siivola]

The branch master has been updated:
       via  e6d5005b43bc3bb70db40df7c103dc637b0dde39 (commit)
      from  4ed03a2e72eea8453e21b54fadb9910c5002bc3f (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit e6d5005b43bc3bb70db40df7c103dc637b0dde39
Author: Nikodemus Siivola <nikodemus at random-state.net>
Date:   Thu Sep 23 18:41:57 2010 +0300

    optimizations to BINOMIAL-COEFFICIENT and COUNT-PERMUATIONS
    
     Patch by Gustavo on alexandria-devel.
    
     Also add tests.

-----------------------------------------------------------------------

Summary of changes:
 numbers.lisp |   14 +++++++++-----
 tests.lisp   |   18 ++++++++++++++++++
 2 files changed, 27 insertions(+), 5 deletions(-)

diff --git a/numbers.lisp b/numbers.lisp
index bf6ef0b..0fa29a4 100644
--- a/numbers.lisp
+++ b/numbers.lisp
@@ -210,6 +210,10 @@ greater then K."
   (if (or (zerop k) (= n k))
       1
       (let ((n-k (- n k)))
+        ;; Swaps K and N-K if K < N-K because the algorithm
+        ;; below is faster for bigger K and smaller N-K
+        (when (< k n-k)
+          (rotatef k n-k))
         (if (= 1 n-k)
             n
             ;; General case, avoid computing the 1x...xK twice:
@@ -231,8 +235,8 @@ greater then K."
 
 (defun count-permutations (n &optional (k n))
   "Number of K element permutations for a sequence of N objects.
-R defaults to N"
-  ;; FIXME: Use %multiply-range and take care of 1 and 2, plus
-  ;; check types.
-  (/ (factorial n)
-     (factorial (- n k))))
+K defaults to N"
+  (check-type n (integer 0))
+  (check-type k (integer 0))
+  (assert (>= n k))
+  (%multiply-range (1+ (- n k)) n))
diff --git a/tests.lisp b/tests.lisp
index c139568..b9e2277 100644
--- a/tests.lisp
+++ b/tests.lisp
@@ -1712,3 +1712,21 @@
   (1 2 3)
   nil
   nil)
+
+(deftest count-permutations.1
+    (values (count-permutations 31 7)
+            (count-permutations 1 1)
+            (count-permutations 2 1)
+            (count-permutations 2 2)
+            (count-permutations 3 2)
+            (count-permutations 3 1))
+  13253058000
+  1
+  2
+  2
+  6
+  3)
+
+(deftest binomial-coefficient.1
+    (alexandria:binomial-coefficient 1239 139)
+  28794902202288970200771694600561826718847179309929858835480006683522184441358211423695124921058123706380656375919763349913245306834194782172712255592710204598527867804110129489943080460154)
-- 
Alexandria hooks/post-receive