[ZT; Prog.] Kettenbrüche, Näherung von Wurzeln

Neue Frage »

Hosenschlange Auf diesen Beitrag antworten »
[ZT; Prog.] Kettenbrüche, Näherung von Wurzeln
Mahlzeit,

ich habe ein kleines Problem mit der Programmierung von Kettenbrüchen zur Annäherung von Quadratwurzeln. Das Ganze ist erstmal in Python. Mit "2" funktioniert das, bei bspw. "13" kackt er aber ab:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
from __future__ import division
from fractions import Fraction
import math

def intsqrt(N):
    ''
    g = (N >> N.bit_length() // 2) + 1
    r = (g + N // g) // 2
    while abs(r - g) > 1:
        g = r
        r = (g + N // g) // 2
    while r * r > N:
        r -= 1
    return r

def approx_cfrac(N, iterations, ret=0):
    ' ret == 0: return as fraction '
    ' ret != 0: return as real '

    r = intsqrt(N)
    if r * r == N: return r

    a = Fraction(r, 1)
    x = Fraction(0, 1)
    num = N - r
    den = r + r

    for i in range(iterations):
        x = num / (x + den)
        print (a+x)             # debug

    a += x
    if ret == 0:
        return a
    else:
        return a.numerator / a.denominator

if __name__ == "__main__":
    ''
    Q = 13
    R = intsqrt(Q)

    print (str(Q) + " --> "  + str(math.sqrt(Q)))
    print (approx_cfrac(Q, 7, 1))

Für Q = 2 und 7 Iterationen erscheinen dann die Brüche
code:
1:
2:
3:
4:
5:
6:
7:
3/2
7/5
17/12
41/29
99/70
239/169
577/408
...und als Näherung 1.4142135516460548.

Für Q = 13 und 7 Iterationen erhalte ich die Brüche
code:
1:
2:
3:
4:
5:
6:
7:
14/3
99/23
367/84
2697/619
9926/2277
73041/16757
268753/61656
...und als Näherung 4.358910730504736, obwohl 3.605551275463989 richtig sein sollte.

Könnte mir bitte jemand auf die Sprünge helfen?
HAL 9000 Auf diesen Beitrag antworten »

Sieht ganz danach aus, als wären das Kettenbrüche von statt welche für . Haben wir da irgendwo ein kleines Vorzeichenproblem? Den Quelltext habe ich noch nicht angeschaut.


Alles klar, der Übeltäter findet sich in Zeile 25: Dort muss num = N-r*r statt nur num = N-r stehen!!! Für mit r=1 ist das nicht aufgefallen, für mit r=3 aber schon...
Hosenschlange Auf diesen Beitrag antworten »

Ich hatte bei stackexchange (?) eine Kurzanleitung für das Beispiel x = 5 gefunden und z. B. auf x = 13 angewendet, wonach ; also . Anhand des Beispiels geht es weiter mit . Daraus folgt , und weiter . Nach Umformung erhalte ich . habe ich auf 0 gesetzt und dann die entsprechende Zahl von Iterationen durchgearbeitet. Dabei erhalte ich ...usw... Das stellt also den Nachkommateil dar.

Wie gesagt...mit x = 2 funktioniert das einwandfrei verwirrt
HAL 9000 Auf diesen Beitrag antworten »

Siehe EDIT.
Hosenschlange Auf diesen Beitrag antworten »

Da steckte also der Hase im Speckmantel! Vielen Dank Freude
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »