64Bit Wurzel

[Robert (Gast)]

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

[STK500-Besitzer (Gast)]

Heron-Verfahren selber programmieren?! (oder hies das anders?)

[6643 (Gast)]

Ja. http://de.wikipedia.org/wiki/Heron-Verfahren

[Christoph db1uq K. (christoph_kessler)]

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

[Kai G. (runtimeterror)]

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?

[6643 (Gast)]

>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

[Kai G. (runtimeterror)]

Xn+1 = (Xn + a / Xn) / 2

In meinem Heron-Verfahren sehe ich ein Shift und eine Division - wie 
sieht dein Heron-Verfahren aus?

[Luther B. (luther-blissett)]

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

[Karl H. (kbuchegg)]

Vor kurzem erst gelernt:
Es gibt ein Verfahren bei dem nur Subtrahiert und Inkrementiert
werden muss.

#include <stdio.h>

int mySqrt( long nr )
{
  int cnt = 0;
  long tmp = 1;

  while( nr >= 0 ) {
    nr = nr - tmp;
    tmp = tmp + 2;
    cnt++;
  }

  return cnt - 1;
}

int main()
{
  printf( "%ld", mySqrt( 876543 ) );
}

Wenn Multiplikationen teuer sind, könnte das Vorteile haben
(habs nicht ausgemessen)

[Detlef _. (detlef_a)]

Bei der Wurzel aus 2^64 läuft die while-Schleife 2^32 Mal, das kann 
dauern.

Cheers
Detlef

[Kai G. (runtimeterror)]

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.

[Karl H. (kbuchegg)]

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!