CODEWITHSUNDEEP
pythonalgorithmcatalan
Reodont
Reodont

Reputation: 329

Python calculating Catalan Numbers

I have code which is calculating catalan numbers with method of Binominal Coefficients. 

def BinominalCoefficient(n,k):
    res = 1;
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res /= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(510))

I have a "nan" result when i try to calculate Catalan number which n is more than 510. Why this is happening? And how can i solve it?

Upvotes: 14

Views: 2508

Answers (2)

Xavier Guihot
Xavier Guihot

Reputation: 61716

In addition to xnx's answer, note that starting Python 3.8, with the addition of math.comb (binomial coefficient) in the standard library, we can also calculate Catalan numbers as such:

import math

def catalan(n):
  return math.comb(2*n, n) / (n+1)

catalan(511) # 2.1902514917394773e+303

Upvotes: 2

xnx
xnx

Reputation: 25548

I assume you're using Python 3.

Your res /= (i + 1) should be res //= (i + 1) to force integer arithmetic:

def BinominalCoefficient(n,k):
    res = 1
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(511))

returns

2190251491739477424254235019785597839694676372955883183976582551028726151813997871354391075304454574949251922785248583970189394756782256529178824038918189668852236486561863197470752363343641524451529091938039960955474280081989297135147411990495428867310575974835605457151854594468879961981363032236839645

You get nan because the divison /= in Python 3 returns a float which overflows to inf.

Upvotes: 11

Related Questions