Thema: Quadratwurzel schnell berechnen

[OsDevNewbie]

Du könntest die x86-Instruktion "sqrtss" verwenden. Sie berechnet eine Quadratwurzel aus einer 32-bit Floating-Point-Zahl und braucht so 13 Zyklen auf modernen Prozessoren. Mit "sqrtps" kannst du sogar 4 Zahlen gleichzeitig berechnen in der gleichen Zeit. Das führt dazu, dass du 13/4 = 3.25, also etwa 4 Zyklen pro Zahl brauchst. Natürlich geht das nur, wenn du SSE verwenden kannst.

[Svenska]

Hast du gemessen oder geschätzt?

[TomCat]

Hast du da auch den Code dazu?
Wäre sehr interessant.

[OsDevNewbie]

Hast du gemessen oder geschätzt?

Ich habe im Intel optimization manual nachgeschaut. Dort sind aber leider nur die Latenzen auf Prozessoren der letzten paar Generationen verfügbar.

Hast du da auch den Code dazu?
Wäre sehr interessant.

Ich habe im Anhang ein C Programm (unkommentiert, aber hoffentlich leicht lesbar), dass auf verschiedene Arten die Wurzel aus einer int Zahl zieht. Bei meiner Testmaschine (i7-4770k mit 32GiB RAM) kommen folgende Ergebnisse raus:

Code: [Auswählen]

Alloziere 3000000000 (11718750.00 KiB) Elemente...OK
Initialisiere...OK
Berechne (calc_sqrt_float_sse)...OK(1.642945 Zyklen/Element)
OK
Berechne (calc_sqrt_float_avx)...OK(1.619843 Zyklen/Element)
OK
Berechne (calc_sqrt_double_sse)...OK(6.353434 Zyklen/Element)
OK
Berechne (calc_sqrt_double_avx)...OK(6.327483 Zyklen/Element)
OK
Berechne (calc_sqrt_float_sse_2x)...OK(1.621323 Zyklen/Element)
OK
Berechne (calc_sqrt_float_avx_2x)...OK(1.625151 Zyklen/Element)
OK
Berechne (calc_sqrt_double_sse_2x)...OK(6.315364 Zyklen/Element)
OK
Berechne (calc_sqrt_double_avx_2x)...OK(6.325675 Zyklen/Element)
Wie du siehst ist es sehr schnell. (Damit die AVX-Funktionen ausgeführt werden musst du beim Compilieren AVX aktivieren).
(Wieso die AVX-Variante gleich schnell ist wie die SSE-Variante verstehe ich selber noch nicht ganz.)
Wenn man die Wurzel aus floats zieht, dann hat man eine Genauigkeit von 24-Bit ich weiss nicht ob dir das reicht. Deshalb hab ich noch die double Varianten davon gemacht, da hat man eine höhere Genauigkeit (wie hoch steht nicht im Manual), aber sind teilweise ein bisschen langsamer.
Du kannst das Programm ja mal bei dir testen und schauen, ob es schnell genug ist für dich.
Du darfst auch von meinem Code kopieren oder mir sagen, wenn ich etwas gemacht habe.

Ich muss noch dazu sagen, dass ich jetzt die Umwandlung zwischen ints und floats in meinen Berechnungen in meinem Post nicht einberechnet habe (die kosten immer so 4 Zyklen pro umwandlung), sie werden aber im Programm mit eingerechnet.