When trying to print pascals triangle 13th iteration prints wrong answer

Question

I'm writing a script in C to print out pascals triangle, so I wrote a function for factorial, then made the variable c = to the binomial expansion equation, this works up until line n = 13 where it produces the output:

1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1 
1 11 55 165 330 462 462 330 165 55 11 1 
1 12 66 220 495 792 924 792 495 220 66 12 1 
0 4 24 88 221 399 532 532 399 221 88 24 4 0

With the last line being n = 13. I originally thought it was breaking because the factorials would be to big for 32bit integers but the error is still present with 64bit integers...

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <inttypes.h>


int64_t factorial(int k);

int main(int argc, char **argv)
{
    int c, n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);

    for (i = 0; i <= n; i++) {
        for (r = 0; r <= i; r++) {
            c = (int) factorial(i) / (factorial(r) * factorial((i - r)));
            printf("%d ", c);
        }
        printf("\n");
    }
    return 1;


}

int64_t factorial(int k)
{
    int64_t j;

    if (k == 0 || k == 1)
        return 1;

    int n = k;

    for (j = k; n > 1;)
        j = j * --n;
    return j;
}

I would greatly appreciate some help with this...

Answer 1

Your computation fails even in 64-bit because you shoot yourself in the foot with a cast (it hurts):

c = (int) factorial(i) / (factorial(r) * factorial((i - r)));

is parsed as

c = ((int)factorial(i)) / (factorial(r) * factorial((i - r)));

Just remove the cast or place it on the result:

c = (int)(factorial(i) / (factorial(r) * factorial(i - r)));

Note that your factorial function is too complicated, here is a simpler version:

int64_t factorial(int n) {
    int64_t x;
    for (x = 1; n > 1; n--) {
        x *= n;
    }
    return x;
}

Note also that you do not need to compute the full factorial, this version goes to 29, and can be further improved with some work:

#include <stdio.h>
#include <stdlib.h>

long long binomial(int n, int p) {
    int q;
    long long x;

    if (p < n - p)
        p = n - p;
    q = n - p;
    for (x = 1; n > p; n--)
        x *= n;
    for (; q > 1; q--)
        x /= q;
    return x;
}

int main(int argc, char **argv)
{
    int n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);

    for (i = 0; i <= n; i++) {
        for (r = 0; r <= i; r++) {
            printf("%lld ", binomial(i, r));
        }
        printf("\n");
    }
    return 0;
}

Finally, if you are allowed to use arrays, computing the Pascal triangle can be further simplified as each coefficient is the sum of the one above it and the one to the left of that one:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
    int n, r, i;

    if (argc < 2) {
        printf("[function]:  %s [number of lines to print]", argv[0]);
        return -1;
    }

    n = atoi(argv[1]);
    long long coeff[n + 1];

    coeff[0] = 1;
    for (r = 1; r <= n; r++) {
        coeff[r] = 0;
    }
    for (i = 0; i <= n; i++) {
        for (r = i; r > 0; r--) {
            coeff[r] += coeff[r - 1];
        }
        for (r = 0; r <= i; r++) {
            printf("%lld ", coeff[r]);
        }
        printf("\n");
    }
    return 0;
}