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.
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.
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.
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…
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.
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?
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 …
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
}