Pascal Triangle in C

Question

So I implemented this Pascal Triangle program in C, and it works well up until the 13th line, where the values onwards are no longer correct. I believe the combination function is correct, a k combination of n elements can be written with factorials, and it says so on the combination Wikipedia page hehe. Here's the code:

#include <stdio.h>

int factorial(int number);
int combination(int n, int k);

int main() {
    int lines;
    int i, j;

    printf("Number of Pascal Triangle lines: ");
    scanf("%d", &lines);

    for (i = 0; i <= lines; i++) {
        for (j = 0; j <= i; j++)
            printf("%d ", combination(i, j));

        printf("\n");
    }
}

int combination(int n, int k) {
    int comb;

    comb = (factorial(n)) / (factorial(k) * factorial(n - k));

    return comb;
}

int factorial(int number) {
    int factorial = 1;
    int i;

    for (i = 1; i <= number; i++)
        factorial = factorial * i;

    return factorial;
}

Answer 1

Hope the following code might help ::

/*elements of the pascal's trianlge for 10 rows*/

#include<stdio.h>
int main()
{
 int p[11][11];
 int i,j,k;

 for(i=1;i<=10;i++)
   {
     /*creating whitespaces*/
     for(k=i;k<=10;k++)
      {
         printf("  ");
      }
     for(j=1;j<=i;j++)
      {
        /*printing the boundary elements i.e. 1*/
        if(j==1 || i==j) 
          {
            p[i][j]=1;
            printf("%3d ",p[i][j]);
          }
        /*printing the rest elements*/
        else
          {
            p[i][j]=p[i-1][j-1]+p[i-1][j];
            printf("%3d ",p[i][j]);
          }   
       }
      printf("\n");
   }
}

Thanks

Answer 2

Your implementation cannot handle even moderately large values of n because factorial(n) causes an arithmetic overflow for n >= 13.

Here is a simplistic recursive implementation that can handle larger values, albeit very slowly:

#include <stdio.h>

int combination(int n, int k) {
    if (n < 0 || k < 0 || k > n)
        return 0;
    if (k == 0 || k == n)
        return 1;
    return combination(n - 1, k - 1) + combination(n - 1, k);
}

int main() {
    int lines, i, j;

    printf("Number of Pascal Triangle lines: ");
    if (scanf("%d", &lines) != 1)
        return 1;

    for (i = 0; i <= lines; i++) {
        for (j = 0; j <= i; j++) {
            printf("%d ", combination(i, j));
        }
        printf("\n");
    }
    return 0;
}

Notes:

• This implementation illustrates how vastly inefficient recursive implementations can become.
• Since you are printing a complete triangle, you should store intermediary results and compute one full line at a time from the previous line very efficiently, but still limited by the range of unsigned long long, 67 lines.

Here is a faster alternative:

#include <stdio.h>

int main() {
    int lines, i, j;

    printf("Number of Pascal Triangle lines: ");
    if (scanf("%d", &lines) != 1 || lines < 0 || lines > 67)
        return 1;

    unsigned long long comb[lines + 1];
    for (i = 0; i <= lines; i++) {
        comb[i] = 0;
    }
    comb[0] = 1;
    for (i = 0; i <= lines; i++) {
        for (j = i; j > 0; j--) {
            comb[j] += comb[j - 1];
        }
        for (j = 0; j <= i; j++) {
            printf("%llu ", comb[j]);
        }
        printf("\n");
    }
    return 0;
}

Answer 3

Computing Pascal's triangle straight from the binomial formula is a bad idea because

• the computation of the factorial in the numerator is overflow-prone,

• every computation requires the evaluation of about n products (k + n - k) and a division (plus n! computed once), for a total of n² per row.

A much more efficient solution is by means of Pascal's rule (every element is the sum of the two elements above it). If you store a row, the next row is obtained with just n additions. And this only overflows when the element value is too large to be representable.

---

In case you only need the n-th row, you can use the recurrence

C(n,k) = C(n,k-1).(n-k+1)/k

This involves 2n additions, n multiplications and n divisions, and can overflow even for representable values. Due to the high cost of divisions, for moderate n it is probably better to evaluate the whole triangle ! (Or just hard-code it.)

If you need a single element, this recurrence is attractive. Use symmetry for k above n/2 (C(n,k) = C(n,n-k)).