Pascal’s Triangle in C

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.