Hallo an alle, Für eine Berechnung wird eine 64 Bit Quadratwurzel benötigt. Ich brauch aber nur Integer Arithmetik, kein Double. Ich hab das ganze schon mit dem GC getestet. Doch da wird die ganze Double Bibliothek dazugelinkt --> 4,6kB Code. Hat jemand ein optimiertes Assembler Listing für eine 64 Bit Wurzel? Danke im Voraus Gruß Robert
Es geht auch mit Cordic, wenn man x=w+1/4, y=w-1/4 setzt http://de.wikipedia.org/wiki/Cordic#Hyperbolische_Modi http://www.mikrocontroller.net/articles/AVR-CORDIC#hyperbolic_vectoring
Wert mit Intervallschachtelung und Rückmultiplikation suchen (weiß nicht, ob das einen Namen hat). Würde ca. 32 mal eine 32x32-Multiplikation erfordern. Ist recht kompakt und leicht zu implementieren. und wegen der schnellen Multiplikation in AVRs nicht allzu langsam (sofern du AVRs nutzt :) ). Heron braucht Divisionen - dürfte daher schlechter performen. Mit Cordic habe ich keine Erfahrungen. Darf ich mal neugierig nachfragen wofür du das brauchst?
>Heron braucht Divisionen - dürfte daher schlechter performen.
Mit Cordic habe ich keine Erfahrungen.
Division ? Wo ? Div 2 ist keine Division, sondern ein Shift_right
Xn+1 = (Xn + a / Xn) / 2 In meinem Heron-Verfahren sehe ich ein Shift und eine Division - wie sieht dein Heron-Verfahren aus?
Im Internet fliegen einige Implementationen herum, die isqrt nur mit shift+logik und schneller als eine Division erledigen, z.B: http://www.cc.utah.edu/~nahaj/factoring/isqrt.c.html Der Algorithmus beruht dabei mehr oder weniger auf John von Neumanns Algorithmus für den ENIAC: http://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm
Vor kurzem erst gelernt: Es gibt ein Verfahren bei dem nur Subtrahiert und Inkrementiert werden muss.
1 | #include <stdio.h> |
2 | |
3 | int mySqrt( long nr ) |
4 | {
|
5 | int cnt = 0; |
6 | long tmp = 1; |
7 | |
8 | while( nr >= 0 ) { |
9 | nr = nr - tmp; |
10 | tmp = tmp + 2; |
11 | cnt++; |
12 | }
|
13 | |
14 | return cnt - 1; |
15 | }
|
16 | |
17 | int main() |
18 | {
|
19 | printf( "%ld", mySqrt( 876543 ) ); |
20 | }
|
Wenn Multiplikationen teuer sind, könnte das Vorteile haben (habs nicht ausgemessen)
Bei der Wurzel aus 2^64 läuft die while-Schleife 2^32 Mal, das kann dauern. Cheers Detlef
Das sieht ja mal handlich aus :) Die Multiplikationen müssten aber arg teuer sein, damit sich das bei 64-Bit-Zahlen lohnt... die Schleife läuft dann ja bis zu 2^32 mal durch :/ Der Algorithmus probiert ja einfach nach der Holzhammermethode alle n² durch. Bis 16 Bits lohnt sich das aber u.U.
Detlef _a wrote: > Bei der Wurzel aus 2^64 läuft die while-Schleife 2^32 Mal, das kann > dauern. :-) Man hat ja Zeit. Und wann rechnet man schon die Wurzel aus 2^64 Im 2-ten von Luther angegebenen Link wird ausgehend vom gleichen Prinzip, die Methode verfeinert. Hochinteressant!
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.