Deepak Malhotra Deepak Malhotra - 1 year ago 126
C++ Question

Floating point error in C++ code

I am trying to solve a question in which i need to find out the number of possible ways to make a team of two members.(note: a team can have at most two person)
After making this code, It works properly but in some test cases it shows floating point error ad i can't find out what it is exactly.

Input: 1st line : Number of test cases
2nd line: number of total person

Thank you

using namespace std;
long C(long n, long r)
long f[n + 1];
f[0] = 1;
for (long i = 1; i <= n; i++)
f[i] = i * f[i - 1];
return f[n] / f[r] / f[n - r];

int main()
long n, r, m,t;
cout<<C(n, min(r, n - r))+1<<endl;
return 0;

Answer Source

You aren't getting a floating point exception. You are getting a divide by zero exception. Because your code is attempting to divide by the number 0 (which can't be done on a computer).

When you invoke C(100, 1) the main loop that initializes the f array inside C increases exponentially. Eventually, two values are multiplied such that i * f[i-1] is zero due to overflow. That leads to all the subsequent f[i] values being initialized to zero. And then the division that follows the loop is a division by zero.

Although purists on these forums will say this is undefined, here's what's really happening on most 2's complement architectures. Or at least on my computer....

At i==21:

f[20] is already equal to 2432902008176640000

21 * 2432902008176640000 overflows for 64-bit signed, and will typically become -4249290049419214848 So at this point, your program is bugged and is now in undefined behavior.

At i==66

f[65] is equal to 0x8000000000000000. So 66 * f[65] gets calculated as zero for reasons that make sense to me, but should be understood as undefined behavior.

With f[66] assigned to 0, all subsequent assignments of f[i] become zero as well. After the main loop inside C is over, the f[n-r] is zero. Hence, divide by zero error.


I went back and reverse engineered your problem. It seems like your C function is just trying to compute this expression:

  R! * (N-R)!

Which is the "number of unique sorted combinations"

In which case instead of computing the large factorial of N!, we can reduce that expression to this:

      [ ∏ i ]

This won't eliminate overflow, but will allow your C function to be able to take on larger values of N and R to compute the number of combinations without error.

But we can also take advantage of simple reduction before trying to do a big long factorial expression

For example, let's say we were trying to compute C(15,5). Mathematically that is:

  10! 5!

Or as we expressed above:

 1*2*3*4*5*6*7*8*9*10  *  1*2*3*4*5

The first 10 factors of the numerator and denominator cancel each other out:


But intuitively, you can see that "12" in the numerator is already evenly divisible by denominators 2 and 3. And that 15 in the numerator is evenly divisible by 5 in the denominator. So simple reduction can be applied:

 1  * 4

There's even more room for greatest common divisor reduction, but this is a great start.

Let's start with a helper function that computes the product of all the values in a list.

long long multiply_vector(std::vector<int>& values)
    long long result = 1;
    for (long i : values)
        result = result * i;
        if (result < 0)
            std::cout << "ERROR - multiply_range hit overflow" << std::endl;
            return 0;
    return result;

Not let's implement C as using the above function after doing the reduction operation

long long C(int n, int r)
    if ((r >= n) || (n < 0) || (r < 0))
        std::cout << "invalid parameters passed to C" << std::endl;
        return 0;

    // compute
    //    n!
    //  -------------
    //   r! *  (n-r)!
    // assume (r < n)

    // Which maps to

    //      n
    //    [∏ i]
    //    n - r
    // --------------------
    //     R!

    int end = n;
    int start = n - r + 1;

    std::vector<int> numerators;
    std::vector<int> denominators;
    long long numerator = 1;
    long long denominator = 1;

    for (int i = start; i <= end; i++)
    for (int i = 2; i <= r; i++)

    size_t n_length = numerators.size();
    size_t d_length = denominators.size();
    for (size_t n = 0; n < n_length; n++)
        int nval = numerators[n];
        for (size_t d = 0; d < d_length; d++)
            int dval = denominators[d];

            if ((nval % dval) == 0)
                denominators[d] = 1;
                numerators[n] = nval / dval;

    numerator = multiply_vector(numerators);
    denominator = multiply_vector(denominators);
    if ((numerator == 0) || (denominator == 0))
        std::cout << "Giving up.  Can't resolve overflow" << std::endl;
        return 0;

    long long result = numerator / denominator;

    return result;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download