# Thread: Problem with nCr - Pascals Triangle

1. ## Problem with nCr - Pascals Triangle

I just made a small prog to work out probabilities. Originally I had an array containing elements of pascals triangle, used by the prog. Since it was quite limited i switched to using the nCr formula I found here: http://ptri1.tripod.com/

I tested the nCr function and it worked as expected, but for some reason when I added it to my prog it suddenly mangles the output. Heres my code:

Code:
```#include <stdio.h>
#include <ctype.h>
void probability();
double power(double num, int exp);
int factoral(int n);
int nCr(int n, int r);
int again();

int main()
{
do
probability();
while(again());
return 0;
}

void probability()
{
const static char tri[5][6] =
{
{1, 1, 0, 0, 0, 0},
{1, 2, 1, 0, 0, 0},
{1, 3, 3, 1, 0, 0},
{1, 4, 6, 4, 1, 0},
{1, 5,10,10, 5, 1}
};

int n=0, i;
double p=-1, q;

printf("Enter a number of events: ");
while(n < 1 || n > 5) scanf("&#37;i", &n);
printf("Enter the probability each events success: ");
while(p<0.0 || p>1.0) scanf("%lf", &p);

q = 1.0 - p;

double p1, q1, r;
for(i=0; i<=n; i++)
{
p1 = power(p, n-i);
q1 = power(q, i);
r =  p1*q1*nCr(n-1, i);   //THIS DOES NOT WORK
//r = tri[n-1][i]*p1*q1;  //BUT THIS DOES
printf("%lf\t%i/%i\n", r, n-i, n);
}
}
double power(double num, int exp)
{
if(! exp) return 1.0;
int i;
double result = num;
for(i=1; i<exp; i++)
result *= num;
return result;
}

int factoral(int n)
{
int i, f=1;
for(i=2; i<=n; i++) f*=i;
return f;
}

int nCr(int n, int r)
{
//     n!
// ___________
//  r! (n-r)!
int a = factoral(n);
int b = factoral(r);
int c = factoral(n-r);
return a / (b * c);
}

int again()
{
char ch = '\0';
while(ch != 'y' && ch != 'n')
{
while((ch=getchar())!='\n');
printf("Run again? (Y/N)");
ch = getchar();
ch = tolower(ch);
}
return(ch == 'y')? 1: 0;
}```
Can anyone tell me why it dosent work?

Thanks.

2. Nevermind I managed to fix it. It was stupidly simple; I just had to remove the -1 >_<

3. Ok I have a different problem now that I cant work out. Since its related to the same prog I figured I'd add it here.

Basically, the progam works but does weird things if you enter lots of events.

On 15 or more events some probabilities become negative, which should not be possible. I got no idea why this would be happening unless it was due to floating point innaccuracy or overflow, but I'm using doubles.

Also if 50 or more events are entered the whole program crashes for me. Heres the code again. You should be able to see what I mean if you test it:
Code:
```#include <stdio.h>
#include <ctype.h>
void probability();
double power(double num, int exp);
int factoral(int n);
int nCr(int n, int r);
int again();

int main()
{
do
probability();
while(again());
return 0;
}

void probability()
{
int n=0, i;
double p=-1, q, p1, q1, result;

printf("Enter a number of events: ");
while(n < 1 || n >99) scanf("%i", &n);
printf("Enter the probability each events success: ");
while(p<0.0 || p>1.0) scanf("%lf", &p);

q = 1.0 - p;

for(i=0; i<=n; i++)
{
p1 = power(p, n-i);
q1 = power(q, i);
result =  p1*q1*(double)nCr(n, i);
printf("%lf\t%i/%i\n", result, n-i, n);
}
}

double power(double num, int exp)
{
if(! exp) return 1.0;
int i;
double result = num;
for(i=1; i<exp; i++)
result *= num;
return result;
}

int factoral(int n)
{
int i, f=1;
for(i=2; i<=n; i++) f*=i;
return f;
}

int nCr(int n, int r)
{
//     n!
// ___________
//  r! (n-r)!
int a = factoral(n);
int b = factoral(r);
int c = factoral(n-r);
return a / (b * c);
}

int again()
{
char ch = '\0';
while(ch != 'y' && ch != 'n')
{
while((ch=getchar())!='\n');
printf("Run again? (Y/N)");
ch = getchar();
ch = tolower(ch);
}
return(ch == 'y')? 1: 0;
}```
How can i tell where the problem is?

Cheers.

4. In nCr(), if b * c overflows you might have issues.

5. I don't see any basis for your claim that you're using doubles, since factoral and nCr are all integer functions. And 15! is 1.3 x 10^12, which requires about 40 bits to store, so integer overflow should happen in that neck of the woods.

6. But there could be a way to compute nCr without going to floating point simply by taking advantage of the divisions and performing less multiplications. However even with such an approach, overflow would not be far...
My thinking: nCr(15,4) = 15!/4!*11! = (12*13*14*15)/(1*2*3*4) which can be computed in an int no?

7. Thanks guys, using long long fixed the problem.

Theres just one more issue. If I enter 30 events all probabilities wind up being 0 (with some as -0 for some reason). Would this be due to limitations with doubles, long long, or is there something else I am doing wrong?

Cheers.

Edit: yeah I guess I'm going to need a big num library if i want to do this sort of stuff. Guess I'll just cap the maximum number of events for now.

8. Stop using built in types! Get a BigInteger library and factorialize your program to infinity.