Rekursive Wurzelberechnung mit Intervallhalbierung

[Dagon]

Hi Leute,
Ich habe folgendes Problem:
Ich will eine Funktion schreiben, die die Wurzel eines gegebenen Radikanten durch rekursive Intervallhalbierung berechnet. Dafür hab ich bisher folgendes:

Code: Alles auswählen

def Intervall(radikant,unten,oben):
    mitte=(unten+oben)/2.0
    print mitte
    if mitte**2 < radikant:              
       unten=Intervall(radikant,mitte,oben)
    else:
       oben=Intervall(radikant,unten,mitte)

Das Problem ist, dass ich keine vernünftige Abbruchbedingung zu Stande bekomme. Es wird zwar eine immer bessere Annäherung ausgegeben (später sogar der genaue Wert) aber irgendwann wiederholt sich das Ergebnis nurnoch bis ein Fehler kommt.
Kann mir da jemand weiterhelfen?

[helmut]

Hallo Dagon,
nachfolgend 2 Loesungen, einmal iterativ und einmal rekursiv.

Code: Alles auswählen

from math import fabs

def iter_sqrt(q_zahl,curval):
	while fabs(q_zahl/curval-curval)>.0001:
		curval = (q_zahl/curval+curval)/2.
	return curval

def rec_sqrt(q_zahl,curval):
	if fabs(q_zahl/curval-curval)<.0001:
		res = curval
	else:
		res = rec_sqrt(q_zahl,(q_zahl/curval+curval)/2.)
	return res

print iter_sqrt(900,10)                      #30.000000014
print rec_sqrt(900, 10)                     #30.000000014

Gruss, Helmut

[Dagon]

Danke auf jeden Fall für die Antwort, nur ist sie nicht ganz das, was ich gesucht habe. Gibt es keine Möglichkeit meiner Funktion noch eine Abbruchbedingung hinzuzufügen, dass sie einfach ab einer bestimmter Schrittzahl/Genauigkeit aufhört? Denn es werden ja die richtigen Näherungswerte ausgegeben, nur halt endlos.

[Joghurt]

Wie wäre es mit

Code: Alles auswählen

if abs(oben-unten)<1e-5

Diese Funktion solltest du aber nicht rekursiv schreiben, da du das jeweilige Ergebnis des rekursiven Aufrufs eh nicht benötigst. (Und du früher oder später einen Stack-overflow produzierst, wenn du zuviele Schritte brauchst)

Warum nicht einfach iterativ (was du praktisch ja eh schon machst)

Code: Alles auswählen

def Intervall(radikant, unten, oben):
  mitte = (unten+oben)/2.0
  while abs(unten-oben)>1e-5:
      mitte = (unten+oben)/2.
      if mitte*mitte < radikant:
        unten = mitte
      else:
        oben = mitte
  return mitte