From f0ae63b072f3404f377f8fae0121c943ce33fc5d Mon Sep 17 00:00:00 2001
From: nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>
Date: Wed, 30 Aug 2017 08:26:16 +0000
Subject: array.c: refine binomial_coefficient

* array.c (binomial_coefficient): get rid of bignums by division
  after each multiplications.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@59692 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
---
 array.c | 15 +++++++++++----
 1 file changed, 11 insertions(+), 4 deletions(-)

diff --git a/array.c b/array.c
index e131d1fc06..9faaa88673 100644
--- a/array.c
+++ b/array.c
@@ -5096,16 +5096,23 @@ descending_factorial(long from, long how_many)
 static VALUE
 binomial_coefficient(long comb, long size)
 {
-    VALUE r, v;
+    VALUE r;
+    long i;
     if (comb > size-comb) {
 	comb = size-comb;
     }
     if (comb < 0) {
 	return LONG2FIX(0);
     }
-    r = descending_factorial(size, comb);
-    v = descending_factorial(comb, comb);
-    return rb_int_idiv(r, v);
+    else if (comb == 0) {
+	return LONG2FIX(1);
+    }
+    r = LONG2FIX(size);
+    for (i = 1; i < comb; ++i) {
+	r = rb_int_mul(r, LONG2FIX(size - i));
+	r = rb_int_idiv(r, LONG2FIX(i + 1));
+    }
+    return r;
 }
 
 static VALUE
-- 
cgit v1.2.3