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

``````#include<iostream>
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;
cin>>t;
while(t--)
{
cin>>n;
r=1;
cout<<C(n, min(r, n - r))+1<<endl;
}
return 0;
}
``````

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.

Update

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

``````   N!
-------------
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:

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

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:

``````   15!
--------
10! 5!
``````

Or as we expressed above:

`````` 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15
-----------------------------------
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:

`````` 11*12*13*14*15
-----------------------------------
1*2*3*4*5
``````

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:

`````` 11*2*13*14*3
-----------------------------------
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++)
{
numerators.push_back(i);
}
for (int i = 2; i <= r; i++)
{
denominators.push_back(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