Python 2.7 - продолжение расширения дроби - понимание ошибки

Question

Я написал этот код, чтобы вычислить продолжение разложения дроби рационального числа N с помощью евклидова алгоритма:

from __future__ import division

def contFract(N):
    while True:
        yield N//1
        f = N - (N//1)
        if f == 0:
            break
        N = 1/f

Если, скажем, N равно 3,245, функция никогда не заканчивается, так как, по-видимому, f никогда не равно 0. Первые 10 членов разложения:

[3.0, 4.0, 12.0, 3.0, 1.0, 247777268231.0, 4.0, 1.0, 2.0, 1.0]

Что явно является ошибкой, поскольку фактическое расширение только:

[3; 4,12,3,1] или [3;4,12,4]

Что является причиной проблемы здесь? Это какая-то ошибка округления?

Answer 1

Проблема в том, что вы тестируете f == 0 (целое число 0), что почти никогда не верно для чисел с плавающей точкой. Так что цикл продолжается вечно.

Вместо этого проверьте некоторую точность, эквивалентную 0 ( что иногда может быть неправильным):

>>> from __future__ import division
>>>
>>> def contFract(N):
...     while True:
...         yield N//1
...         f = N - (N//1)
...         if f < 0.0001:  # or whatever precision you consider close enough to 0
...             break
...         N = 1/f
...
>>>
>>> list(contFract(3.245))
[3.0, 4.0, 12.0, 3.0, 1.0]
>>>

И в случае f может быть отрицательным, либо -0.0001 < f < 0.0001 или же abs(f) < 0.0001, Что также считается неточным, см. Статью по ссылке.

И по поводу моего комментария использовать int(N) вместо N//1 потому что это понятнее - это немного менее эффективно:

>>> import timeit
>>> timeit.timeit('N = 2.245; N//1', number=10000000)
1.5497028078715456
>>> timeit.timeit('N = 2.245; int(N)', number=10000000)
1.7633858824068103

Answer 2

Ты используешь float для вашей работы, к сожалению, некоторые числа не могут быть представлены как числа в двоичном представлении.

Есть два варианта, как это исправить, во-первых - предположим, что ваши цифры "достаточно близки" (даже в новой версии Python 3.5.2 math.isclose), или вы используете другую реализацию поплавков, например Decimal Вы можете получить правильные результаты.

Поэтому для всех финансовых систем никто никогда не использует числа с плавающей запятой, только int/bigint или Decimals.

 In [21] > N = decimal.Decimal('3.245')

 In [22] > while True:
    print 'N: %s' % (N//1,)
    f = N - N//1
    print 'f: %s' % f
    if f == 0:
        break
    N = 1/f

N: 3
f: 0.245
N: 4
f: 0.081632653061224489795918367
N: 12
f: 0.25000000000000000000000005
N: 3
f: 0.999999999999999999999999200
N: 1
f: 8.00E-25
N: 1250000000000000000000000
f: 0

Answer 3

По-видимому, ошибка связана с целочисленным делением 4.0 на 1. 4.0 в представлении с плавающей точкой содержит ошибку (если у вас есть представление о представлении с плавающей точкой). Таким образом, на самом деле int(4.0) < 4. Это приводит к тому, что N//1 становится равным 3,0, а дробь f выглядит как 0.999999.... Так что это никогда не заканчивается. Выведите N и f в каждой итерации и поиграйте. Вы поймете.