CODEWITHSUNDEEP
javadoublecombinations
Chen Xie
Chen Xie

Reputation: 4271

Java: Combination function yields decimal number

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?

Upvotes: 0

Views: 290

Answers (2)

Alanyst
Alanyst

Reputation: 1410

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.

Upvotes: 2

user000001
user000001

Reputation: 33377

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

Upvotes: 1

Related Questions