Evaluate binomial coefficients: Difference between revisions
Content added Content deleted
(→{{header|Java}}: add more implementations, especially some reliable ones) |
|||
Line 1,126: | Line 1,126: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
<lang java>public class Binomial |
<lang java>public class Binomial { |
||
{ |
|||
// precise, but may overflow and then produce completely incorrect results |
|||
private static long |
private static long binomialInt(int n, int k) { |
||
⚫ | |||
if (k>n-k) |
if (k > n - k) |
||
k=n-k; |
k = n - k; |
||
⚫ | |||
long |
long binom = 1; |
||
for (int i |
for (int i = 1; i <= k; i++) |
||
binom = binom * (n + 1 - i) / i; |
|||
return |
return binom; |
||
} |
} |
||
// same as above, but with overflow check |
|||
⚫ | |||
private static Object binomialIntReliable(int n, int k) { |
|||
⚫ | |||
if (k > n - k) |
|||
⚫ | |||
long binom = 1; |
|||
for (int i = 1; i <= k; i++) { |
|||
try { |
|||
binom = Math.multiplyExact(binom, n + 1 - i) / i; |
|||
} catch (ArithmeticException e) { |
|||
return "overflow"; |
|||
} |
|||
⚫ | |||
return binom; |
|||
} |
} |
||
⚫ | |||
{{Out}} |
|||
<pre>10</pre> |
|||
// using floating point arithmetic, larger numbers can be calculated, |
|||
{{trans|Python}} |
|||
// but with reduced precision |
|||
<lang java>public class Binom { |
|||
private static double binomialFloat(int n, int k) { |
|||
if (k > n - k) |
|||
k = n - k; |
|||
⚫ | |||
double binom = 1.0; |
|||
for (int i = 1; i <= k; i++) |
|||
binom = binom * (n + 1 - i) / i; |
|||
return binom; |
|||
⚫ | |||
// slow, hard to read, but precise |
|||
private static BigInteger binomialBigInt(int n, int k) { |
|||
if (k > n - k) |
|||
k = n - k; |
|||
BigInteger binom = BigInteger.ONE; |
|||
for (int i = 1; i <= k; i++) { |
|||
binom = binom.multiply(BigInteger.valueOf(n + 1 - i)); |
|||
binom = binom.divide(BigInteger.valueOf(i)); |
|||
} |
} |
||
return |
return binom; |
||
⚫ | |||
⚫ | |||
List<Object> data = Arrays.asList( |
|||
n, |
|||
k, |
|||
binomialInt(n, k), |
|||
binomialIntReliable(n, k), |
|||
binomialFloat(n, k), |
|||
binomialBigInt(n, k)); |
|||
System.out.println(data.stream().map(Object::toString).collect(Collectors.joining("\t"))); |
|||
} |
} |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
demo(5, 3); |
|||
demo(1000, 300); |
|||
} |
} |
||
⚫ | |||
} |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>10.0 |
<pre>5 3 10 10 10.0 10 |
||
1000 300 -8357011479171942 overflow 5.428250046406143E263 542825004640614064815358503892902599588060075560435179852301016412253602009800031872232761420804306539976220810204913677796961128392686442868524741815732892024613137013599170443939815681313827516308854820419235457578544489551749630302863689773725905288736148678480</pre> |
|||
Recursive version: |
Recursive version, without overflow check: |
||
<lang java>public class Binomial |
<lang java>public class Binomial |