Python calculate factorial, OverflowError: int too large to convert to float

Question

I want to write a function that calculate (1 / n!) * (1! + 2! + 3! + ... + n!) with n as the parameter of the function, also the result is truncated to 6 decimals (not rounded). Below is my code:

def going(n):
    n1 = n 
    n2 = n
    factorial = 1
    back = 1
    for i in range(2, n1+1):
        factorial *= i
    while n2>1:
        this = 1
        for i in range(2, n2+1):
            this*=i
        back+=this
        n2 = n2-1
        this = 1
    result = int((1/factorial)*back*1000000)/1000000
    return result

When I passed the argument 171 into the function, I got the following traceback:

Traceback (most recent call last):
  File "/Users/Desktop/going.py", line 18, in <module>
    print(going(171))
  File "/Users/Desktop/going.py", line 15, in going
    result = int((1/factorial)*back*1000000)/1000000
OverflowError: int too large to convert to float

How can I fix this problem? Thanks a lot for help!

--update-- Sorry that I didn't clarify: I'm doing this problem in Codewars and I don't think I can import any libraries to use. So, I need a solution that can avoid using any libraries.

Original problem from Codewars:

Consider the following numbers (where n! is factorial(n)):

u1 = (1 / 1!) * (1!)
u2 = (1 / 2!) * (1! + 2!)
u3 = (1 / 3!) * (1! + 2! + 3!)
un = (1 / n!) * (1! + 2! + 3! + ... + n!)

Which will win: 1 / n! or (1! + 2! + 3! + ... + n!)?

Are these numbers going to 0 because of 1/n! or to infinity due to the sum of factorials?

Task

Calculate (1 / n!) * (1! + 2! + 3! + ... + n!) for a given n, where n is an integer greater or equal to 1.

To avoid discussions about rounding, return the result truncated to 6 decimal places, for example:

1.0000989217538616 will be truncated to 1.000098 1.2125000000000001 will be truncated to 1.2125

Remark

Keep in mind that factorials grow rather rapidly, and you need to handle large inputs.

Try in the IRB `2**9999` vs `float(2**9999)` – dawg Dec 16 '18 at 05:12 — dawg, Dec 16 '18 at 05:12
can u post original and full problem from codewars? – Saiful Azad Dec 16 '18 at 06:00 — Saiful Azad, Dec 16 '18 at 06:00

score 4 · Answer 1 · answered Dec 16 '18 at 05:06

And going(170) works as intended, right?

What you are seeing is a fundamental limitation of how your computer represents floating point numbers, and not a problem with Python per se. In general, most modern computers use IEEE 754 to represent and perform math with non-integer numbers. Specifically, numbers using IEEE 754's "binary64" (double-precision) floating point representation has a maximum value of 2^1023 × (1 + (1 − 2^−52)), or approximately 1.7976931348623157 × 10^308. It turns out that 170! ≈ 7.2 × 10^306, which is just under the maximum value. However, 171! ≈ 1.2 × 10^309, so you are out of luck.

The best chance you have of actually performing calculations with numbers that large without running into these overflow errors or losing precision is to use a large number library like gmpy2 (see this previous answer). A possible solution would be:

from gmpy2 import mpz, add, div, fac
def going(n):
    factorial = fac(n)
    back = mpz(1)
    for i in range(2, n+1):
        back = add(back, fac(i))
    result = div(back, factorial)
    return result

Thank you. But I'm doing this problem in Codewars and I don't think I can import any libraries, do you have any other solutions? — Triansan, Dec 16 '18 at 05:47

Warren Weckesser · Accepted Answer · 2018-12-16T06:18:40.320

@PaSTE's suggestion to use gmpy2 is great, and should work fine.

The library mpmath is built on top of gmpy2 and provides the function ff (falling factorial) that makes the implementation a little more concise:

import mpmath

def going_mp(n):
    return sum([1/mpmath.ff(n, k) for k in range(n)])

For example,

In [54]: import mpmath

In [55]: mpmath.mp.dps = 30

In [56]: going_mp(170)
Out[56]: mpf('1.00591736819491744725806951204519')

In [57]: going_mp(171)
Out[57]: mpf('1.00588255770874220729390683925161')

(I left out the truncating of the digits. That's something that you can add as you see fit.)

Another standard technique for handling very large numbers is to work with the logarithms of the numbers instead of the numbers themselves. In this case, you can use math.lgamma to compute k!/n! as exp(lgamma(k+1) - lgamma(n+1)). This will allow you to compute the value using just the standard math library.

import math

def going_l(n):
    lognfac = math.lgamma(n + 1)
    return sum([math.exp(math.lgamma(k+1) - lognfac) for k in range(1, n+1)])

For example,

In [69]: going_l(170)
Out[69]: 1.0059173681949172

In [70]: going_l(171)
Out[70]: 1.0058825577087422

Finally, if you don't want to use even the standard library, you could avoid the large numbers another way. Rewrite the expression as

       1      1           1                 1
   1 + - + ------- + ------------- + ... + ---
       n   n*(n-1)   n*(n-1)*(n-2)          n!

That leads to this implementation:

def going_nolibs(n):
    total = 0.0
    term = 1.0
    for k in range(n, 0, -1):
        total += term
        term /= k
    return total

For example,

In [112]: going_nolibs(170)
Out[112]: 1.0059173681949174

In [113]: going_nolibs(171)
Out[113]: 1.0058825577087422

Python calculate factorial, OverflowError: int too large to convert to float

2 Answers2