diff options
author | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2017-08-30 08:26:16 +0000 |
---|---|---|
committer | nobu <nobu@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2017-08-30 08:26:16 +0000 |
commit | f0ae63b072f3404f377f8fae0121c943ce33fc5d (patch) | |
tree | c0cdfa71c1fbe8b53b38a534bd0c39a9efdba6c2 /array.c | |
parent | 96223329d0b11a76e37a91b08a828571b5e97172 (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.c | 15 |
1 files changed, 11 insertions, 4 deletions
@@ -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 |