Returns n choose k, also known as the binomial coefficient of n and k, that is, n! / (k! (n - k)!). Warning: the result can take as much as O(k log n) space. @throws IllegalArgumentException if n < 0, k < 0, or k > n
(int n, int k)
| 425 | |
| 426 | |
| 427 | public static BigInteger binomial(int n, int k) { |
| 428 | checkNonNegative("n", n); |
| 429 | checkNonNegative("k", k); |
| 430 | checkArgument(k <= n, "k (%s) > n (%s)", k, n); |
| 431 | if (k > (n >> 1)) { |
| 432 | k = n - k; |
| 433 | } |
| 434 | if (k < LongMath.biggestBinomials.length && n <= LongMath.biggestBinomials[k]) { |
| 435 | return BigInteger.valueOf(LongMath.binomial(n, k)); |
| 436 | } |
| 437 | BigInteger accum = BigInteger.ONE; |
| 438 | long numeratorAccum = n; |
| 439 | long denominatorAccum = 1; |
| 440 | int bits = LongMath.log2(n, RoundingMode.CEILING); |
| 441 | int numeratorBits = bits; |
| 442 | for (int i = 1; i < k; i++) { |
| 443 | int p = n - i; |
| 444 | int q = i + 1; |
| 445 | |
| 446 | // log2(p) >= bits - 1, because p >= n/2 |
| 447 | if (numeratorBits + bits >= Long.SIZE - 1) { |
| 448 | // The numerator is as big as it can get without risking overflow. |
| 449 | // Multiply numeratorAccum / denominatorAccum into accum. |
| 450 | accum = |
| 451 | accum.multiply(BigInteger.valueOf(numeratorAccum)).divide(BigInteger.valueOf(denominatorAccum)); |
| 452 | numeratorAccum = p; |
| 453 | denominatorAccum = q; |
| 454 | numeratorBits = bits; |
| 455 | } else { |
| 456 | // We can definitely multiply into the long accumulators without overflowing them. |
| 457 | numeratorAccum *= p; |
| 458 | denominatorAccum *= q; |
| 459 | numeratorBits += bits; |
| 460 | } |
| 461 | } |
| 462 | return accum.multiply(BigInteger.valueOf(numeratorAccum)).divide(BigInteger.valueOf(denominatorAccum)); |
| 463 | } |
| 464 | |
| 465 | // Returns true if BigInteger.valueOf(x.longValue()).equals(x). |
| 466 |
nothing calls this directly
no test coverage detected