Leo - 7 months ago 52

C Question

I'm a computer engineering student and next semester I am going to start C course. So in order to prepare myself a bit, I have started learning C by myself and stumbled across an interesting task, designed for, how it seemed to me at first sight, not a very advanced level.

The task is to write a program to compute the value of a given position in **Pascal's Triangle**. And the formula given to compute it is written as **element = row! / ( position! * (row - position)! )**

I've written a simple console program that seems to work okay, until I get to testing it with **large** numbers.

When trying this program with row 16 and position 3, it calculates the value as 0, although it's obvious that there can't be such a value (in fact it should compute the value as 560), all cells of this triangle are supposed to be integers and be greater than one.

I suppose I'm experiencing a problem with **storing and processing large numbers**. The factorial function seems to work okay, and the formula I used works until I get to trying large numbers

So far the best solution was found here - How do you printf an 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's 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

Factorials get really big really fast (scroll down a little to see the list). Even a 64-bit number is only good up to `20!`

. So you have to do a little preprocessing before you start multiplying.

The general idea is to factor the numerator and the denominator, and remove all of the common factors. Since the results of Pascal's Triangle are always integers, you are guaranteed that the denominator will be 1 after all common factors have been removed.

For example let's say you have `row=35`

and `position=10`

. Then the calculation is

```
element = 35! / 10! * 25!
```

which is

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

So the first simplification is that the larger factorial in the denominator cancels all of the smaller terms of the numerator. Which leaves

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

Now we need to remove the remaining common factors in the numerator and denominator. It helps to put all the number of the numerator in an array. Then, for each number in the denominator, compute the greatest common divisor (gcd) and divide the numerator and denominator by the gcd.

The following code demonstrates the technique.

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

Here's what the code does step by step

```
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
```

When all is said and done the array ends up as

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

Multiply those numbers together and the answer is `183579396`

, and the entire calculation could be performed using 32-bit ints. In general, as long as the answer fits into 32-bits, the calculations can be done with 32-bits.