Deepak Malhotra - 21 days ago 3x

C++ Question

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;

}

Answer

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;
}
```

Source (Stackoverflow)

Comments