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

я написал этот код, чтобы вычислить непрерывную дробь рационального числа N, используя алгоритм Евклида:Python 2.7 - продолжение Фракции Expansion - Понимание ошибки

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]

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

источник

2016-06-29 ggordon

Проблема в том, что вы тестируете 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

источник

2016-06-29 11:08:17 aneroid

Я не понимаю, что вы остановились, 'N // 1' не эквивалентно' N' т.е. 3.223 // 1 = 3. – ggordon

Опять же я не вижу вашу точку, если я используйте 'int (N)' вместо 'N // 1' Я получаю ту же ошибку. С 'N = 1/f' я пытаюсь получить обратную f, а не использовать разделение полов. Если я печатаю 1/f для первых 10 расширений, я получаю: '4.08163265306 12.25 4.0 1.0 2.47777268231e + 11 4,73320814676 1,36386918834 2,74824038982 1,33646888567 2.97204301075' – ggordon

Ах, хорошо, я вижу вашу точку сейчас had't еще не видел изменения в свой пост – ggordon

-1

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

источник

2016-06-29 11:32:04 Mihir

Вы используете 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

источник

2016-06-29 11:33:31 Jerzyk

Хорошее предложение использовать 'math.isclose', но, как вы указали, это Python 3.x, а OP использует будущее подразделение, поэтому он/она находится на Py2k. – aneroid

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

ответ

Смежные вопросы