Pascal's Triangle

[Aaron]

Hi,

I have written a pascals triangle program. However, my program gets a
floating point exception somewhere between 60 and 70 and any subsequent
larger value. This is no doubt due to dividing two large numbers in
the nCr function. By using uint64_t instead of int helped get it this
far. I would like to see if it is possible to use it for larger
values. Unlike with most programs, execution time is of absolutely no
concern. Does anyone have any ideas? Here is my code:

#include <math.h>
#include <stdint.h>
#include <stdio.h>

uint64_t factorial(int n)
{
int i;
uint64_t result=1;

for (i=1; i<=n; i++)
{
result = result * i;
}

return(result);
}

uint64_t partial_factorial(int n, int r)
{
int i;
uint64_t result=1;

for (i=r+1; i<=n; i++)
{
result = result * i;
}

return(result);
}

uint64_t nCr(int n, int r)
{
return(partial_factorial(n,r)/factorial(n-r));
}

int main(int argc, char *argv[])
{
if (argc != 2)
{
printf("usage: pascal <integer>\n");
exit(-1);
}

int size = atoi(argv[1]);

if (size <= 0)
{
printf("Please enter integers greater than 0\n");
exit(-1);
}

uint64_t bc;
int i,j;

for (i=0; i<size; i++)
{
printf("\n");
for (j=0; j<=i; j++)
{
bc = nCr(i, j);
printf("%lld ", bc);
}
}

printf("\n");
}

 

[Ksitami]

/ n \ / n \
| | == | |
\ r / \n-r/
r= min(r, n-r);
or beter
if (2*r > n) r= n - r;

 

[Michael]

I have written a pascals triangle program. However, my program gets a

floating point exception somewhere between 60 and 70 and any subsequent
larger value. This is no doubt due to dividing two large numbers in
the nCr function. By using uint64_t instead of int helped get it this
far. I would like to see if it is possible to use it for larger
values. Unlike with most programs, execution time is of absolutely no
concern. Does anyone have any ideas? Here is my code:

uint64_t nCr(int n, int r)
{
return(partial_factorial(n,r)/factorial(n-r));
}

I would suggest you use the identities nCr = (n-1)C(r-1) + (n-1)Cr,
plus xC0 = xCx = 1 (either iterative or recursive implementation).
That way you're adding reasonable sized numbers, rather than
calculating two huge numbers and dividing them by each other.

Michael

 

[Thad Smith]

I have written a pascals triangle program. However, my program gets a
floating point exception somewhere between 60 and 70 and any subsequent
larger value. This is no doubt due to dividing two large numbers in
the nCr function. By using uint64_t instead of int helped get it this
far. I would like to see if it is possible to use it for larger
values.

You are evaluating n!/(r! * (n-r)!).

The partial factorial is a step in the right direction. You can start
dividing before you finish the partial factorial. Perform the
operations in the following order:

n / 1 * (n-1) / 2 * (n-3) / 3 ... (n-r+1)/r

The largest intermediate value is n!/((r-1)!*(n-r)!).

 

[Duncan Muirhead]

Hi,

I have written a pascals triangle program. However, my program gets a
floating point exception somewhere between 60 and 70 and any subsequent
larger value. This is no doubt due to dividing two large numbers in
the nCr function. By using uint64_t instead of int helped get it this
far. I would like to see if it is possible to use it for larger
values. Unlike with most programs, execution time is of absolutely no
concern. Does anyone have any ideas? Here is my code:

<snip>
If you want to fill the triangle, Michael's method is the way to go;
64 bits will get you up to 67Cr, 128 bits up to 131Cr.

If you want to compute a few (approximate) values of nCr you could use the
lgamma function from the math library:
static double ncr( int n, int r)
{ return exp( lgamma(n+1)-lgamma(r+1)-lgamma(n-r+1));
}
Note though you'll need to use something bigger than a double for n>1029;
1029C514 is 1.4298207e+308, while the above routine returns inf for
1030C515.
Duncan