How to do large number calculation involving factorials in python? [duplicate]

Question

I encountered a problem where I have to do the following calculation:

N = 250
H = 140
bayes_factor = factorial(H) * factorial(N-H) / factorial(N+1) / (0.5**N)

How to solve the problem: I tried:

from scipy.special import factorial
bayes_factor = (factorial(H) * factorial(N-H)) / factorial(N+1) / (0.5**N)

It gives infinity.

Update: typo fixed in the denominator factorial(H+1) should be factorial(N+1).

Note: the answer should come around 0.5 as the coin might be unbiased.

The answer is appreciated.

Does this link solve your question? stackoverflow.com/questions/16996527/… — Dominique
– Dominique, Commented Apr 3, 2019 at 14:28
You don't calculate it directly. You start by recognizing that factorial(H)/factorial(H+1) is just 1/(H+1). — chepner
– chepner, Commented Apr 3, 2019 at 14:28
Stirling's Approximation says 110! is ~ 10^176 (that would be factorial(N-H) as you have N and H defined). I suspect these values are too absurdly large to realistically work with for you. — Jordan Singer
– Jordan Singer, Commented Apr 3, 2019 at 14:33
This is a simple coin toss example, out of 250 toss we get 140 heads, we want to know whether the coin in biased or not. — BhishanPoudel
– BhishanPoudel, Commented Apr 3, 2019 at 14:34
For this question as it is written, the reason why you're making this calculation almost doesn't matter. The point is, as you are trying to solve the problem, the values Python has to keep track of blow up extremely quickly. — Jordan Singer
– Jordan Singer, Commented Apr 3, 2019 at 14:35

OmG · Accepted Answer · 2019-04-03 16:12:37Z

2

For exact solution you can use the following implementation of the factorial which is mentioned in this post:

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def tree_factorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)

Hence, your program will be:

N = 250
H = 140
bayes_factor = tree_factorial(H) * tree_factorial(N-H) / tree_factorial(N+1) / (0.5**N)

You can run the code here. The result is:

Python 3.6.1 (default, Dec 2015, 13:05:11)
[GCC 4.8.2] on linux
bayes_factor: 0.476723359160760
running time: 0.000546

edited Apr 3, 2019 at 16:12

answered Apr 3, 2019 at 16:03

OmG

19k13 gold badges69 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

dmuir · Accepted Answer · 2019-04-03 15:36:21Z

2

You'd be best to work in logarithms, using the scipy.special function loggamma. The gamma function satisfiles

n! = gamma( n+1)

So the expression you gave can be computed as

exp( loggamma( H+1) + loggamma( N-H+1) - loggamma( N+2) - N*log(0.5))

The reason for working in logarithms is that the intermediate terms, for example factorial(N+1) will be so gigantic as to overflow in a double.

answered Apr 3, 2019 at 15:36

dmuir

4,4512 gold badges17 silver badges12 bronze badges

Collectives™ on Stack Overflow

How to do large number calculation involving factorials in python? [duplicate]

2 Answers 2

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Linked

Related