Python 2.7 - Kettenbruch Expansion - Das Verständnis der Fehler

Question

ich diesen Code geschrieben haben, die weitere Bruchentwicklung einer rationalen Zahl berechnen N die euklidische Algorithmus:

from __future__ import division 

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

Wenn sagen N 3.245 ist die Funktion nie als scheinbar endet f nie 0. die ersten 10 Glieder der Entwicklung gleich ist:

[3.0, 4.0, 12.0, 3.0, 1.0, 247.777.268.231,0, 4,0, 1,0, 2,0, 1,0]

die eindeutig ein Fehler, da die tatsächliche Erweiterung ist nur:

[3; 4,12,3,1] oder [3; 4,12,4]

Was das verursacht hat Problem hier? Ist das ein Rundungsfehler?

Answer 1

Das Problem ist, Sie testen f == 0 (Integer 0), die fast nie für Floats gilt. So läuft die Schleife für immer weiter.

Stattdessen prüfen einige Präzision entspricht 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] 
>>> 

Und falls f negativ sein kann, tun entweder -0.0001 < f < 0.0001 oder abs(f) < 0.0001. Was ebenfalls als ungenau angesehen wird, finden Sie im verlinkten Artikel.

Und wrt meinen Kommentar int(N) statt N//1 zu verwenden, weil es klarer ist - es leicht ist weniger effizient:

>>> 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

Anscheinend ist der Fehler ist aufgrund der Integer-Division von 4,0 um 1 4.0 in floating Punktdarstellung hat einen Fehler (wenn Sie eine Vorstellung von Gleitkommadarstellung haben). Also eigentlich int (4.0) < 4. Dies bewirkt, dass das N // 1 3.0 wird und der Bruchteil f etwa 0.999999 .... Also endet das nie. Drucke die N und f in jeder Iteration und spiele herum. Du wirst es merken.

Answer 3

Sie verwenden float für Ihre Operation, leider können einige der Zahlen nicht als eine Zahl in Binärdarstellung dargestellt werden.

gibt es zwei Möglichkeiten, wie Sie es beheben, zuerst - nehmen Sie an, dass Ihre Zahlen "nahe genug" sind (sogar neue Python 3.5.2 führt math.isclose ein), oder Sie verwenden unterschiedliche Implementierung von Floats, z. Decimal können Sie korrekte Ergebnisse erhalten.

N.b. Aus diesem Grund verwendet niemand für alle Finanzsysteme Floats, nur int/bigint oder 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