summaryrefslogtreecommitdiff
path: root/array.c
diff options
context:
space:
mode:
authornobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-08-30 08:26:16 (GMT)
committernobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e>2017-08-30 08:26:16 (GMT)
commitf0ae63b072f3404f377f8fae0121c943ce33fc5d (patch)
treec0cdfa71c1fbe8b53b38a534bd0c39a9efdba6c2 /array.c
parent96223329d0b11a76e37a91b08a828571b5e97172 (diff)
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
Diffstat (limited to 'array.c')
-rw-r--r--array.c15
1 files changed, 11 insertions, 4 deletions
diff --git a/array.c b/array.c
index e131d1f..9faaa88 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