Java: Combination function yields decimal number

Question

I was trying to implement a simple combination function

private int combination(int n, int k)
{
    if(n>>1 < k)
        k = n - k;
    double mul = 1;
    for(int i=n+1-k;i<n+1;i++)
        mul *= i;
    for(int i=k;i>0;i--)
        mul /= i;
    return (int)mul;
}

When I feed in parameters as combination(33,17), it gives me 1166803109, though the correct number should be 1166803110. So I printed out the mul variable before truncating to int, and it gives me a decimal number: 1.1668031099999998E9, which is confusing to me. By definition it should be a perfect division, why it gives me a decimal?

http://stackoverflow.com/questions/177506/why-do-i-see-a-double-variable-initialized-to-some-value-like-21-4-as-21-3999996 — Brian Roach, Feb 14 '13 at 04:31
[What Every Computer Scientist Should Know About Floating-Point Arithmetic](http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html). To avoid this problem maybe start using [BigDecimal](http://docs.oracle.com/javase/7/docs/api/java/math/BigDecimal.html) — Pshemo, Feb 14 '13 at 04:37

Alanyst · Accepted Answer · 2013-02-14T04:47:06.480

When it comes to floating-point types like float or double, there's rarely perfect division (perfect in the sense that the floating-point result is a whole number). This is because of the way that the values are represented internally; there is some loss of precision when the computation is carried out. (It's similar to why the division 2/3 will be rendered by computers as 0.666667.) Rather than use double, stick with an integral type like int or long, or else use BigInteger or similar if your computation might reach values larger than a long can hold.

user000001 · Answer 2 · 2013-02-14T04:31:24.920

1

Due to their internal representation, Floating point arithmetic is not entirely accurate.

Since you are only interested in an integer representation of the result, you can round the double, instead of truncating, with Math.round()

Your method should become like this:

private int combination(int n, int k)
{
    if(n>>1 < k)
        k = n - k;
    double mul = 1;
    for(int i=n+1-k;i<n+1;i++)
        mul *= i;
    for(int i=k;i>0;i--)
        mul /= i;
    return (int) Math.round(mul);
}

Output:

System.out.println(combination(33,17));

1166803110

edited Feb 14 '13 at 04:31

answered Feb 14 '13 at 04:26

user000001

32,226
12
81
108

`Math.round` is not the best solution here. In edge cases it could pick the wrong way to round and introduce subtle accuracy bugs. Use an integral type for `mul` rather than a floating point type. – Alanyst Feb 14 '13 at 04:34
@Alanyst Can you think of any example of this case? – user000001 Feb 14 '13 at 04:35
In the case where the algorithm ensures that the the divisor is a factor of the dividend, it probably won't happen. So, the fear of accuracy problems using `Math.round` is probably unfounded, and you're right to question me on that. However, I think it's still the less optimal choice; integral values are much faster to compute than floating-point values that are then coerced to integral values using a rounding computation. – Alanyst Feb 14 '13 at 04:46
Ok leaving the answer here in case OP does not want to change the footprint of his method. – user000001 Feb 14 '13 at 04:49

Java: Combination function yields decimal number

2 Answers2