Python 2.7 - продолжение Фракции Expansion - Понимание ошибки

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 (which can be wrong sometimes):

>>> 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. Который также считается неточным, см. Связанную статью.

И WRT моего комментария использовать 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

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

Answer 3

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

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

N.b. поэтому для всех финансовых систем никто никогда не использует float, только 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