Работа с повышенной точностью иррациональных чисел в python

Question

Я пытаюсь сделать continued fraction derivation иррациональных чисел, например. sqrt (13), с Python. Я получил довольно хорошее решение, которое является точным в течение первых 10 или около того итераций:

1. Установите оригинальный номер в качестве текущего остатка
2. Append пола текущего остатка к списку коэффициентов
3. Определить новый остаток как взаимный ток остатка минус пол
4. Перейти к шагу 2, если новый остаток не 0

Это работает очень хорошо, для последующих итераций, гдекроме Точностьпорождает ошибочные коэффициенты. Как только один коэффициент выключен, остальные будут автоматически также.

Мой вопрос, поэтому, если есть способ лечения иррациональных чисел, например. sqrt (13), например, заполнители (для последующей замены) или более точно?

Мой текущий код, как показано ниже:

import math 


def continued_fraction(x, upper_limit=30): 
    a = [] 
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit): 
     a.append(int(x)) 
     x = 1.0/(x - a[-1]) 
    return a 


if __name__ == '__main__': 
    print continued_fraction(math.sqrt(13)) 

С результатом выхода:

[3, 1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 6, 
    1, 1, 1, 1, 7, 2, 1, 4, 2] 

И я знаю, за то, что полученный результат должен быть 3, а затем бесконечных повторений цикл (1, 1, 1, 1, 6), согласно Project Euler Problem 64 (который я пытаюсь решить).

Answer 1

Я не знаю таких заполнителей в Python.

Однако вы можете использовать decimal.Decimal, что увеличит точность ваших математических операций, но никогда не гарантирует бесконечных повторений цикла. Зачем? Is floating point math broken?

Следующая модификация кода дает правильные результаты для этого не разбежались до upper_limit=45:

import math 
from decimal import Decimal 


def continued_fraction(x, upper_limit=30): 
    a = [] 
    # should in fact iterate until repetitive cycle is found 
    for i in range(upper_limit): 
     a.append(int(x)) 
     x = Decimal(1.0)/(x - a[-1]) 
    return a 


if __name__ == '__main__': 
    print (continued_fraction(Decimal(13).sqrt())) 

Answer 2

Вы можете бросить взгляд на https://rosettacode.org/wiki/Continued_fraction#Python. Он использует модули Fractions и Itertools.

Answer 3

По-видимому, Marius Becceanu выпустил an algorithm for the specific continued fraction of sqrt(n), что является итеративным и очень приятным. Этот алгоритм не требует использования каких-либо плавающих точек.