www.mikrocontroller.net

Forum: Mikrocontroller und Digitale Elektronik 64Bit Wurzel


Autor: Robert (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: STK500-Besitzer (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Heron-Verfahren selber programmieren?! (oder hies das anders?)

Autor: 6643 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Christoph Kessler (db1uq) (christoph_kessler)
Datum:

Bewertung
0 lesenswert
nicht lesenswert

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: 6643 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Xn+1 = (Xn + a / Xn) / 2

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

Autor: Luther Blissett (luther-blissett)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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/bjsd...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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)

Autor: Detlef _a (detlef_a)
Datum:

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

Cheers
Detlef

Autor: Kai G. (runtimeterror)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.