python - Неточный результат при вычислении числа Каталана


2

В чем может быть проблема при просчете чисел Каталана? На больших числах возникает неточность, т.е на 45 числе выводит 2257117854077247679365120, а должно быть 2257117854077248073253720.

arr = [1]
def Catalan(n):
    global arr
    while(len(arr) != n+1):
        arr.append(int(int(arr[len(arr)-1] ) * (4*len(arr)-2)/(len(arr)+1) ) )
    print(arr[n])
Источник
  •  33
  •  2
  • 25 янв 2017 2017-01-25 11:04:04
def Catalan(n): arr = [1] for j in range(1,n+1): total = [] for i in range(j): final = arr[i]*arr[j-1-i] total.append(final) fin = sum(total) arr.append(fin) print(arr[n]) Вот такой код. Деления нет, но все равно при числе 45 выводит ложный результат. В чем может быть проблема? — 10 янв 20182018-01-10 09:28:57.000000
Пролистал документацию, написано, что с третьей версии int не имеет границ, а использовал при написании 3.5. — 25 янв 20172017-01-25 10:56:47.000000
@VasylKolomiets, судя по меткам питон третий, но там есть деление: (4*len(arr)-2)/(len(arr)+1). — 25 янв 20172017-01-25 10:56:25.000000
@Kromster, если тут всё целочисленное, он должен сам перейти на biginteger. Про дробные не знаю. — 25 янв 20172017-01-25 10:53:14.000000
А какой тип используется в Питоне для работы с числами, Double какой-нибудь, с точностью до 18 знаков? — 25 янв 20172017-01-25 10:34:35.000000

2 ответа

9
(4*len(arr)-2)/(len(arr)+1) )
#             ^ вот поэтому

В Python 3 / выполняет деление с плавающей точкой. А точность двойных чисел с плавающей точкой ограничена примерно 15-17 десятичными цифрами, аккурат после которых (15) у вас и наблюдается разница.

См. также "Вычисления на числах с плавающей точкой не работают"

1 / 1 # => 1.0

Если заменить его на //, целочисленное деление (которое в Python 2 выполнялось оператором /, если операнды были целочисленными), результаты станут ожидаемыми. Поэтому, кстати, этот алгоритм прекрасно работает в Python 2 (если не импортировать "деление из будущего").


И выкиньте int(...)ы. Там и так будут целые числа.

  • 25 янв 2017 2017-01-25 15:11:42
1

Удобнее реализовывать подобные функции по рекурентным формулам, например если взять третью рекурентную формулу из википедии, получим следующую функцию:

import functools


@functools.lru_cache(maxsize=None)
def catalan(n):
    if n == 0:
        return 1
    return catalan(n-1)*2*(2*n-1)//(n+1)

Результат для 45: 2257117854077248073253720

точно, затупил) — 28 янв 20172017-01-28 12:49:03.000000
каждое catalan(n-1) будет вычислять n до n == 0. — 27 янв 20172017-01-27 11:08:09.000000
Если требуется вычислить одно число, то думаю нет необходимости, так как повторных вычислений не будет. А так да, хорошее дополнение. — 27 янв 20172017-01-27 10:03:21.000000
lru_cache следовало бы добавить. — 25 янв 20172017-01-25 22:32:14.000000