Wurzel ziehen ohne dividiren

Wissenschaft Informatik
#1

Hallo ich suche eine formel zum wurzel ziehen ohne Dividieren zu müssen. Möchte ein programm in C machen und da division immer sehr lage dauern wollte ich mir das ersparren bzw meinen arbeits kollegen, die das schon mal probiert aber nicht sehr erfolgreich hinbekommen haben. habe 2 wege gefunden aber mein wissen in c (sehr schwach) reicht nicht um die um zu setzen. stehe da noch ganz am anfang.

hier mal die formel

http://www.tinohempel.de/info/mathe/wurzel/wurzel.htm

wenn jemand den namen dieser formel kennt wäre mir auch schon recht geholfen.

vielen dank.

#2

Hallo,

gibt es einen guten Grund, nicht die sqrt()-Funktion (bzw sqrtf(), sqrtl()) aus der C-Standarbibliothek zu nehmen?

Die ist normalerweise schon ziemlich schnell, und rechnet auch richtig.

Grüße,
Moritz

#3

Moien

Möchte ein programm in C machen und da division
immer sehr lage dauern

Es gibt einen extrem schnellen Ansatz: die Quake3 InvSqrt-Funktion. Aber man braucht eine Division um auf Sqrt zu kommen und genau ist was anderes…

cu

#4

Hi Sebastian,

die Formel (oder besser das Verfahren) heisst Heron-Verfahren (steht auch oben auch der Seite). Inwiefern dir das allerdings helfen soll weiß ich nicht, denn du musst offensichtlich alle 4 Grundrechenarten verwenden um zu bestimmen.

Grüße,
JPL

#5

Hallo ich suche eine formel zum wurzel ziehen ohne Dividieren
zu müssen. Möchte ein programm in C machen und da division
immer sehr lage dauern wollte ich mir das ersparren bzw meinen
arbeits kollegen, die das schon mal probiert aber nicht sehr
erfolgreich hinbekommen haben. habe 2 wege gefunden aber mein
wissen in c (sehr schwach) reicht nicht um die um zu setzen.
stehe da noch ganz am anfang.

hier mal die formel

http://www.tinohempel.de/info/mathe/wurzel/wurzel.htm

Einen Algorithmus des schriftlichen Rechnens zu programmieren und dann von Effizenz zu Reden ist ein Widerspruch in sich. Kein Programmier kommt auf diese Idee. Die simpelste Lösung ist eine Intervallhalbierung, wo man das Quadrat auf den Radikanten prüft. Eine hinreichen effektive Lösung dürfte die Newton-Verfahren sein, das wesentlich schneller konvergiert, siehe Wikipedia…

Gruß HW

#6

Summe(2n+1)=m²
Hallo Sebastian,

möglicherweise ist das Toeplerverfahren etwas für Dich:

Dinglers Polytechnisches Journal, 1866 Reuleaux, F.: Prof. Toepler’s Verfahren der Wurzelausziehung mittelst der Thomas’schen Rechenmaschine. S. 260ff

Schrader, B. (1953)
Abgekürztes Toeplerverfahren zum Quadratwurzelziehen mit der Rechenmaschine.
Mitt. des Deutschen Vereins für Vermessungswesen, Landesverein Baden 5 (1953), Heft 1, Seite 29-32.

Im Wesentlichen beruht es darauf, das nacheinander die ungeraden Zahlen von dem Radikanden abgezogen werden. Dabei wird mitgezählt, wie oft abgezogen wird. Dann gibt es noch Spezialbehandlungen, wenn die Zahl viele Stellen hat.

Wenn Du da was brauchst, dann hab ich auch was, was ich einscannen kann.

Viele Grüße
Stefan

#7

Hallo Hans,

Einen Algorithmus des schriftlichen Rechnens zu programmieren
und dann von Effizenz zu Reden ist ein Widerspruch in sich.
Kein Programmier kommt auf diese Idee.

Sofern einem nur die Möglichkeit zur Verfügung steht, in Hochsprache zu programmieren, stimme ich Dir zu. Hat man dagegen direkt die Möglichkeit, die Zahlen in den Registern hin und herzuschieben, dann gibt es tatsächlich schnellere Möglichkeiten als iterative Algorithmen.

Die simpelste Lösung
ist eine Intervallhalbierung, wo man das Quadrat auf den
Radikanten prüft. Eine hinreichen effektive Lösung dürfte die
Newton-Verfahren sein, das wesentlich schneller konvergiert,
siehe Wikipedia…

Das sind genauso wie das Heronverfahren iterative Verfahren, die in jedem Schritt die ganze Zahl eingen Rechenoperationen aussetzen.

Für einen weiteren Einblick das hier:
http://www.rechnerlexikon.de/artikel/Quadratwurzel
Das Toeplerverfahren, sowie die dazu ähnliche Fünfermethode ist natürlich an das Dezimalsystem angepasst. Da bleibt die Frage offen: Kann man das Prinzip des Toeplerverfahrens an Binärzahlen anpassen?

Viele Grüße
Stefan

#8

Moien

Sofern einem nur die Möglichkeit zur Verfügung steht, in
Hochsprache zu programmieren, stimme ich Dir zu. Hat man
dagegen direkt die Möglichkeit, die Zahlen in den Registern
hin und herzuschieben, dann gibt es tatsächlich schnellere
Möglichkeiten als iterative Algorithmen.

Iterative sind aber sehr beliebt, auch unter den CPU-Bauern. Die Gleitkommadivision wird z.B. oft gar nicht implementiert. FDIV Befehle werden als Marko ausgeführt das zuerst eine Näherung aus einer Tabelle holt und dann ein paar Runden verfeinert. So ist auch der Pentium-I Bug entstanden: die Näherungen in der Tabelle waren teilweise falsch, deshalb hat das SRT-Verfahren versagt.

Bei sqrt kommt das gleiche Prinzip zum Einsatz. Der Quake3-Ansatz ist deshalb so genial weil er die Näherung ohne anschliessendes verfeinern ausrechnet. Man hat also eine passable Näherung in 3x mul, 2x sub und einem shift. Zur Not kann man ja noch 2-3 Runden Näherungen rechnen …

cu

#9

Hallo Sebastian,

Hallo ich suche eine formel zum wurzel ziehen ohne Dividieren
zu müssen. Möchte ein programm in C machen und da division
immer sehr lage dauern wollte ich mir das ersparren bzw meinen
arbeits kollegen, die das schon mal probiert aber nicht sehr
erfolgreich hinbekommen haben. habe 2 wege gefunden aber mein
wissen in c (sehr schwach) reicht nicht um die um zu setzen.
stehe da noch ganz am anfang.

Das ergibt alles keinen Sinn (für mich). Was möchtest
Du denn genau machen? Warum (und wo) dauern denn
Divisionen „sehr lange“? Was willst Du denn genau
ausrechnen? Mit diesen Informationen könnte man Dir
wahrscheinlich eher weiterhelfen.

Um welche Zahlen handelt es sich? Ganze Zahlen (Integer)?
Warum kann man eine Division nicht durch eine Multi-
plikation mit einem Kehrwert ersetzen?

Grüße

CMБ

P.S.: das hier schon mehrfach erwähnte „Quake-Verfahren“
zur Berechnung von 1.0/sqrt(x) ist ist schon älter
als Quake:

 double InvSqrt( double dx ) {
 // This calculates double( 1 / sqrt( fx ) )
 // by Newtown-Raphson steps
 double xh = 0.5 \* dx;
 uint64\_t ix = \*(uint64\_t \*) &dx;
 ix = 0x5FE6EC85E7DE30DAULL - (ix \>\> 1);
 dx = \*(double \*) &ix;
 // dx \*= (1.5f - xh \* dx \* dx); // one more cycle
 // dx \*= (1.5f - xh \* dx \* dx); // one more cycle
 return dx \*= (1.5f - xh \* dx \* dx); // one more cycle
 // www.lomont.org/Math/Papers/2003/InvSqrt.pdf
}
#11

So hab ich das ganze auch verstanden

Warum lange herumrechnen?

mfg

febner1

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]