(gelöst) [C++] Schnelle Quadratwurzel aus binärer Zweierpote
Verfasst: 18.07.2010, 16:00
Hi,
Algorithmen für Quadratwurzeln gibt es wie Sand am Meer. Im Binärsystem auch. Aber gibt es eine schnelle Variante, die nur mit Zweierpotenzen funktioniert?
Das Vorgehen ist sehr einfach: man halbiert einfach die Anzahl der Nullen hinter der Eins: 100 0000 0000 (1024) -> 10 0000 (32); 10000 (16) -> 100 (4).
Wie kriegt man das möglichst schnell (sprungfrei?) hin?
Ich habe beim Verfolgen des log2-Weges den bsr-x86-Befehl gefunden. Ich müsste nur sein Ergebnis halbieren und als Links-Shift auf 1 anwenden, aber, wie bekommt man einen C++-Compiler dazu, von diesem Befehl Gebrauch zu machen? Assembler ist keine Option, Intrinsics vielleicht.
Gruß, Ky
Edit: thx@Jörg
Algorithmen für Quadratwurzeln gibt es wie Sand am Meer. Im Binärsystem auch. Aber gibt es eine schnelle Variante, die nur mit Zweierpotenzen funktioniert?
Das Vorgehen ist sehr einfach: man halbiert einfach die Anzahl der Nullen hinter der Eins: 100 0000 0000 (1024) -> 10 0000 (32); 10000 (16) -> 100 (4).
Wie kriegt man das möglichst schnell (sprungfrei?) hin?
Ich habe beim Verfolgen des log2-Weges den bsr-x86-Befehl gefunden. Ich müsste nur sein Ergebnis halbieren und als Links-Shift auf 1 anwenden, aber, wie bekommt man einen C++-Compiler dazu, von diesem Befehl Gebrauch zu machen? Assembler ist keine Option, Intrinsics vielleicht.
Gruß, Ky
Edit: thx@Jörg