Autor Thema: Quadratwurzel schnell berechnen  (Gelesen 3511 mal)

OsDevNewbie

  • Beiträge: 281
    • Profil anzeigen
    • YourOS Kernel
Gespeichert
« Antwort #20 am: 25. February 2017, 23:12 »
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.
Viele Grüsse
OsDevNewbie

Ein Computer ohne Betriebsystem ist nicht mehr wert als ein Haufen Schrott.
Ein Computer ist eine Maschine, die einem Lebewesen das kostbarste klaut, was sie selber nicht hat:
DIE ZEIT DES LEBENS

Svenska

  • Beiträge: 1 778
    • Profil anzeigen
Gespeichert
« Antwort #21 am: 26. February 2017, 17:20 »
Hast du gemessen oder geschätzt?

TomCat

  • Beiträge: 32
    • Profil anzeigen
Gespeichert
« Antwort #22 am: 27. February 2017, 09:11 »
Hast du da auch den Code dazu?
Wäre sehr interessant. :-)

OsDevNewbie

  • Beiträge: 281
    • Profil anzeigen
    • YourOS Kernel
Gespeichert
« Antwort #23 am: 01. March 2017, 14:12 »
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:
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.
Viele Grüsse
OsDevNewbie

Ein Computer ohne Betriebsystem ist nicht mehr wert als ein Haufen Schrott.
Ein Computer ist eine Maschine, die einem Lebewesen das kostbarste klaut, was sie selber nicht hat:
DIE ZEIT DES LEBENS

 

Einloggen