Python вычисляет факториал, OverflowError: int слишком велик для преобразования в float

Question

Я хочу написать функцию, которая вычисляет (1 / n!) * (1! + 2! + 3! + ... + n!) С n в качестве параметра функции, также результат усекается до6 десятичных знаков (не округлено).Ниже мой код:

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

Когда я передал аргумент 171 в функцию, я получил следующую трассировку:

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

Как я могу решить эту проблему?Большое спасибо за помощь!

- update-- Извините, что не уточнил: я делаю эту проблему в Codewars и не думаю, что смогу импортировать какие-либо библиотеки для использования.Итак, мне нужно решение, которое поможет избежать использования каких-либо библиотек.

Исходная проблема из Codewars:

Рассмотрим следующие числа (где n! - факториал (n)):

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

Который победит: 1 / n!или (1! + 2! + 3! + ... + n!)?

Эти числа равны 0 из-за 1 / n!или в бесконечность из-за суммы факториалов?

Задание

Вычислить (1 / n!) * (1! + 2! + 3! + ... ...+ n!) для данного n, где n - целое число, большее или равное 1.

Чтобы избежать дискуссий о округлении, верните усеченный результат до 6 десятичных знаков, например:

1.0000989217538616 будет усечено до 1.000098 1.2125000000000001 будет усечено до 1.2125

Примечание

Имейте в виду, что факториалы растут довольно быстро, и вам необходимо обрабатывать большие входные данные.

Answer 1

@ PaSTE предлагает использовать gmpy2 замечательно и должно работать нормально.

Библиотека mpmath построена поверх gmpy2 и предоставляет функцию ff (понижающий факториал), котораяделает реализацию немного более лаконичной:

import mpmath

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

Например,

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')

(я пропустил усечение цифр. Это то, что вы можете добавить по своему усмотрению.)

---

Другой стандартный метод обработки очень больших чисел заключается в работе с логарифмами чисел вместо самих чисел.В этом случае вы можете использовать math.lgamma для вычисления k!/n! как exp(lgamma(k+1) - lgamma(n+1)).Это позволит вам вычислить значение, используя только стандартную библиотеку math.

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)])

Например,

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

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

---

Наконец, если вы не хотитеиспользуйте даже стандартную библиотеку, вы можете избежать больших чисел другим способом.Перепишите выражение как

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

Это приводит к этой реализации:

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

Например,

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

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

Answer 2

И going(170) работает как задумано, верно?

То, что вы видите, является фундаментальным ограничением того, как ваш компьютер представляет числа с плавающей запятой, а не проблемой с Python per se ,Как правило, большинство современных компьютеров используют IEEE 754 для представления и выполнения математических операций с нецелыми числами.В частности, числа, использующие IEEE 754 «binary64» (двойная точность) представление с плавающей запятой, имеют максимальное значение 2 ^ 1023 × (1 + (1 - 2 ^ −52)) или приблизительно 1,7796931348623157 × 10^ 308.Оказывается, 170!≈ 7.2 × 10 ^ 306, что чуть ниже максимального значения.Однако 171!≈ 1,2 × 10 ^ 309, так что вам не повезло.

Наилучший шанс на самом деле выполнить вычисления с большими числами, не сталкиваясь с этими ошибками переполнения или потери точности, - это использовать библиотеку большого числа, такую ​​как gmpy2 (см. этот предыдущий ответ ).Возможное решение будет:

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