64Bit Wurzel

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?

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!