Choose function returns negative values if n >= 13

Question

I'm trying to compute and display some rows of Pascal's Triangle in Python, using Numpy. I have this code:

#Calculates the binomial coefficient from given values
def binomial(n,k):
    #n = int(input("Please input an integer value for n: "))
    #k = int(input("Please input an integer value for k: "))
    factorial = np.ones([1,3],int)
    for a in range(1,n+1):
        factorial[:,0] *=a
    for b in range(1,k+1):
        factorial[:,1] *=b
    for c in range(1,(n-k+1)):
        factorial[:,2] *=c
    solution = int(factorial[:,0]//(factorial[:,1]*factorial[:,2]))
    #print(solution)
    return solution

#Prints Pascal's triangle
def part_b():
    print(1)
    rows = 13  #desired numer of rows
    for n in range(1,rows+1): #iterate for each desired line
        line = [1]
        for k in range(1,n+1): #iterate for position on line
            solution = binomial(n,k)
            line.append(solution)
        print(*line, sep=" ")    
    return

Starting from the 13th row, the result is clearly incorrect. It may even include negative numbers, which makes no sense as the code only multiplies and divides positive integers.

Why does this happen, and how do I fix it?

Answer 1

In Python, integers are unbounded. It means you can have integers as big as your memory can handle.

However, Numpy is written in C, and is designed to use C's integer types for calculations. In C, there is a limit on the value of integers. Results that exceed that value cause integer overflow.

In particular, 13! (the factorial of 13) does not fit in a 32-bit C integer, so the calculation performed by Numpy will overflow.

To avoid the problem, simply don't use Numpy for the calculation.

Answer 2

As the other answer suggested, you could use Python numbers instead of NumPy numbers. You can additionally optimize your code by canceling out some of the factorials beforehand.

Note that n! / (k! * (n-k)!) can also be represented as (n! / k!) / (n-k)!, so you could reduce (n! / k!) to n * (n-1) * (n-2) ... (k+1). Moreover, if n-k > k you can perform this substitution using n-k instead of k, essentially swapping the factorials, making it (n! / (n-k)!) / k!.

#Calculates the binomial coefficient from given values
def binomial(n,k):

    # determines the bigger value to use for k! or (n-k)!
    target_k = max(n-k, k)

    reduced_n_fac = 1
    for i in range(target_k+1, n+1):
        reduced_n_fac *= i

    other_fac = 1
    for i in range(1,(n-target_k+1)):
        other_fac *= i
    return reduced_n_fac // other_fac

This both removes the negative outputs and makes the code faster to make up for the lack of NumPy.