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 binomial(int n, int k)
private static long binomialInt(int n, int k) {
{
if (k>n-k)
if (k > n - k)
k=n-k;
k = n - k;

long b=1;
long binom = 1;
for (int i=1, m=n; i<=k; i++, m--)
for (int i = 1; i <= k; i++)
b=b*m/i;
binom = binom * (n + 1 - i) / i;
return b;
return binom;
}
}


// same as above, but with overflow check
public static void main(String[] args)
private static Object binomialIntReliable(int n, int k) {
{
System.out.println(binomial(5, 3));
if (k > n - k)
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;
}
}
}</lang>
{{Out}}
<pre>10</pre>


// using floating point arithmetic, larger numbers can be calculated,
{{trans|Python}}
// but with reduced precision
<lang java>public class Binom {
public static double binomCoeff(double n, double k) {
private static double binomialFloat(int n, int k) {
double result = 1;
if (k > n - k)
for (int i = 1; i < k + 1; i++) {
k = n - k;

result *= (n - i + 1) / i;
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 result;
return binom;
}

private static void demo(int n, int k) {
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) {
System.out.println(binomCoeff(5, 3));
demo(5, 3);
demo(1000, 300);
}
}
}</lang>
}
</lang>
{{Out}}
{{Out}}
<pre>10.0</pre>
<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