Неправильно высчитывается цепная дробь, что делать?

Question

на картинке, то что должно получиться:

def confract(num):
    den = 1
    a, q = divmod(num, den)
    t = den
    res = [a]
    while q != 0:
        next_t = q
        a, q = divmod(t, q)
        t = next_t
        res.append(a)
    return res

m = 21299881
print(confract(sqrt(m))

получается вот такой массив(по началу все нормально, но после 13 чисел массивы расходятся в значениях):

[4615.0, 5.0, 1.0, 1.0, 2.0, 1.0, 7.0, 1.0, 27.0, 1.0, 6.0, 1.0, 2.0, 13.0, 3.0, 1.0, 7.0, 1.0, 3.0, 8.0, 1.0, 5.0, 1.0, 9.0, 2.0]

Answer 1

тоже точность плывет :(

на 14 члене уже не то

[4615, 5, 1, 1, 2, 1, 7, 1, 27, 1, 6, 1, 2, 13, 3, 1, 7, 1, 2, 1, 12, 2, 2, 4, 10, 2, 2, 1, 5, 1]

вот код

import math

def confract(num, depth = 10):
    res = []
    for _ in range(depth):
        res.append(math.floor(num))
        fraction = num - math.floor(num)
        num = 1 / fraction

    return res


m = 21299881
print(confract(math.sqrt(m), 20), sep=' ')

а с decimal все нормально

[4615, 5, 1, 1, 2, 1, 7, 1, 27, 1, 6, 1, 2, 12, 23, 1, 8, 2, 3, 6, 1, 1, 1, 4, 1, 7, 1, 1, 1, 39, 1, 2, 5, 1, 1, 2, 4, 2, 3, 1]

вот код

import decimal

def confract(num, depth = 10):
    res = []
    for _ in range(depth):
        res.append(int(num))
        fraction = num - int(num)
        num = 1 / fraction

    return res


m = 21299881
print(confract(decimal.Decimal(m).sqrt(), 40), sep=' ')

Answer 2

проблема в точности float поэтому лучше использовать Decimal

import decimal

def confract(num):
    den = 1
    a, q = divmod(num, den)
    t = den
    res = [int(a)]
    while q != 0:
        next_t = q
        a, q = divmod(t, q)
        t = next_t
        res.append(int(a))
    return res

m = decimal.Decimal(21299881)
print(confract(m ** decimal.Decimal("0.5")))

вывод:

[4615, 5, 1, 1, 2, 1, 7, 1, 27, 1, 6, 1, 2, 12, 23, 1, 8, 2, 3, 6, 1, 1, 1, 4, 1, 7, 1, 1, 1, 43, 3, 4, 2, 1, 1, 11, 1, 7, 1, 4, 5, 2, 2, 4, 4, 4]

Answer 3

В дополнение к предыдущим ответам, мне стало интересно - а вдруг достаточно будет и встроенных расширенных типов float из библиотеки Numpy и точный тип Decimal в данной задаче не нужен? Взял за основу код Zhihar:

import numpy as np
from decimal import Decimal

def confract(num, maxlen=14):
    res = np.zeros(maxlen, dtype=np.int)
    for i in range(maxlen):
        n = np.floor(num)
        res[i] = n
        fraction = num - n
        num = 1 / fraction
    return res

m = 21299881
maxlen=100
types = [Decimal, np.float32, np.float64, np.float128]
res = np.zeros((len(types), maxlen), dtype=np.int)
for i,t in enumerate(types):
    r = confract(np.sqrt(t(m)), maxlen)
    res[i,:] = r

exact_result = res[0,:]
print('Расхождение с Decimal после элемента:')
for i,t in enumerate(types[1:], 1):
    print(t.__name__, '-', np.argwhere(res[0,:] != res[i,:])[:1][0][0])

На выходе:

Расхождение с Decimal после элемента:
float32 - 6
float64 - 13
float128 - 16

Таким образом, даже использования довольно длинного типа Numpy.float128 недостаточно для данной задачи - расхождение будет уже после 16-го элемента.

БЛОГ НА HUSL

Неправильно высчитывается цепная дробь, что делать?

Ответы (3 шт):