Pascal's Triangle in C

Question

I am a student of computer engineering, and in the next semester I am going to start a course C. Therefore, to prepare a little, I began to study C myself and came across an interesting task, developed, as it seemed to me, at first glance, not a very advanced level.

The task is to write a program to calculate the value of a given position in the Pascal Triangle . And the formula given for the calculation is written as element = row! / (Position! * (Line - position)!)

I wrote a simple console program that seems to work fine until I post it with large numbers.

When trying this program with line 16 and position 3, it calculates the value as 0, although it is obvious that there cannot be such a value (in fact, it should calculate the value as 560), all cells of this triangle must be integer and be more than one.

I suppose I was having a problem storing and processing large numbers . The factorial function seems to work fine, and the formula I use works until I get an attempt at large numbers

So far, the best solution has been found here - How do you print unsigned long long int (format specifier for unsigned long long int)? using inttypes.h library with type uint64_t, but it still doesn't give me the result I need.

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

void clear_input(void);
uint64_t factorial(int x);

int main()
{
    // Printing
    printf("This program computes the value of a given position in Pascal Triangle.\n");
    printf("You will be asked for row and position of the value.\n");
    printf("Note that the rows and positions starts from 0.\n");
    printf("\n");
    printf("     1          * 0 \n");
    printf("    1 1         * 1 \n");
    printf("   1 2 1        * 2 \n");
    printf("  1 3 3 1       * 3 \n");
    printf(" 1 4 6 4 1      * 4 \n");
    printf(" ****************   \n");
    printf(" 0 1 2 3 4          \n");
    printf("\n");

    // Initializing
    int row, pos;

    // Input Row
    printf("Enter the row: ");
    scanf("%d", &row);
    clear_input();

    // Input Position
    printf("Enter the position in the row: ");
    scanf("%d", &pos);
    clear_input();

    // Initializing
    uint64_t element, element_1, element_2, element_3, element_4;

    // Previously written as -> element = ( factorial(row) ) / ( factorial(pos) * factorial(row - pos) );
    // Doesn't fix the problem
    element_1 = factorial(row);
    element_2 = factorial(pos);
    element_3 = factorial(row - pos);
    element_4 = element_2 * element_3;

    element = element_1 / element_4;

    // Print result
    printf("\n");
    printf("%"PRIu64"\n", element_1);   // Temporary output
    printf("%"PRIu64"\n", element_2);   // Temporary output
    printf("%"PRIu64"\n", element_3);   // Temporary output
    printf("%"PRIu64"\n", element_4);   // Temporary output
    printf("\n");
    printf("The element is %"PRIu64"", element);
    printf("\n");

    return 0;
}

void clear_input(void)                                          // Temporary function to clean input from the keyboard
{
  while(getchar() != '\n');
}

uint64_t factorial(int x)                                       // Function to calculate factorial
{
    int f = 1, i = x;
    if (x == 0) {
        return 1;
    }
    while (i != 1) {
        f = f * i;
        i = i - 1;
    }
    return f;
}

Answer 1

( , ). 64- 20!. , , .

, . Pascal Triangle , , 1 .

, , row=35 position=10.

element = 35! / 10! * 25!

35 * 34 * 33 * ... * 26 * 25 * 24 * ... * 3 * 2 * 1
---------------------------------------------------
     10!                * 25 * 24 * ... * 3 * 2 * 1   

, , .

35 * 34 * 33 * ... * 26 
-----------------------
 10 * 9 * 8 * ... * 1     

. . (gcd) gcd.

.

array[10] = { 35, 34, 33, 32, 31, 30, 29, 28, 27, 26 };  

for ( d = 10; d >= 2; d-- )
{ 
    temp = d;
    for ( i = 0; i < 10 && temp > 1; i++ )
    {
        common = gcd( array[i], temp );
        array[i] /= common;
        temp /= common;
    }
}

d=10   i=0   temp=10   array[0]=35  ==>  gcd(35,10)=5, so array[0]=35/5=7  and temp=10/5=2
d=10   i=1   temp=2    array[1]=34  ==>  gcd(34, 2)=2, so array[1]=34/2=17 and temp=2/2=1
inner loop breaks because temp==1
d=9    i=0   temp=9    array[0]=7   ==>  gcd(7,9)=1,  so nothing changes
d=9    i=1   temp=9    array[1]=17  ==>  gcd(17,9)=1, so nothing changes
d=9    i=2   temp=9    array[2]=33  ==>  gcd(33,9)=3, so array[2]=11 and temp=3
d=9    i=3                          ==>  gcd(32,3)=1
d=9    i=4                          ==>  gcd(31,3)=1
d=9    i=5   temp=3    array[5]=30  ==>  gcd(30,3)=3, so array[5]=10 and temp=1
inner loop breaks

,

array[10] = { 1, 17, 11, 1, 31, 1, 29,  14, 3, 26 }

, 183579396, 32- int. , , 32 , 32-.

Answer 2

( C , )

uint64_t, int. f uint64_t, , .

, (uint64_t 21!). , . row = 16 position = 3 16!/(3! * 13!). (16!/13! 14 * 15 * 16) 14 * 15 * 16/(1 * 2 * 3). 21.

Answer 3

, 64- , , int . :

uint64_t factorial(uint64_t x)
{
    uint64_t f = 1, i = x;
    if (x == 0) {
        return 1;
    }
    while (i != 1) {
        f = f * i;
        i = i - 1;
    }
    return f;
}

, , , . , :

element = (factorial (row)/factorial (pos))/factorial (row-pos);

.

, factorial (row)/factorial (pos) , (), factorial (pos), .

Answer 4

:

#include <stdio.h>

int main()
    {
    printf ("\n");
    int n = 10;
    int i;
    int j;
    int x[n];

    for (i = 0; i < n; i++)
         x[i] = 0;

    for (i = 1; i <= n; i++)
         {
         for (j = n - 1; j >= 1; j--)
              x[j] = x[j-1] + x[j];

         x[0] = 1;

         int s = n - i;

         for (j = 0; j < s; j++)
              printf ("  ");

         for (j = 0; j < n; j++)
              {
              if (x[j] != 0)
                  printf (" %3d", x[j]);
              }

        printf ("\n");
        }

    printf ("\n");
    return 0;
    }