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

Oh! Thanks, changing to a long int should solve the issue then? — m_botto, Mar 16 '18 at 01:22
Time to [learn how to debug your programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). And learn more about [the standard arithmetic types](http://en.cppreference.com/w/c/language/arithmetic_types) and their ranges. — Some programmer dude, Mar 16 '18 at 01:23
That'll get you to about row 20 (assuming that a `long int` is 64-bits). Check out [this question](https://stackoverflow.com/questions/28058019/pascals-triangle-in-c). — user3386109, Mar 16 '18 at 01:24
@user3386109 **If** `long int` is a 64-bit type, which it doesn't have to be. — Some programmer dude, Mar 16 '18 at 01:24
The alternative is to not calculate each element as a combination at all, but in terms of the corresponding values in the previous row. — dbush, Mar 16 '18 at 01:25
@Someprogrammerdude True, I added that caveat to my comment. — user3386109, Mar 16 '18 at 01:26

score 2 · Answer 1 · 2018-03-16T08:33:12.960

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)).

chqrlie · Answer 2 · 2018-03-16T08:52:33.823

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

Gollum · Answer 3 · 2018-04-01T17:08:26.327

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

Pascal Triangle in C

3 Answers3