Fast inverse square root

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

 

sinjin

Betreff: Fast inverse square root

BeitragSa, Sep 05, 2015 23:37
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe diesen Source-Code genommen und den in BMAX umgewandelt, habe mich damit nicht super beschäftigt und musste am Ende noch 1/x rechnen (edit: klar, wegen INVERSED) aber es funktioniert:
Code: [AUSKLAPPEN]
function qsqr#(src#)
  local x2#=src*0.5
  local i%=$5f3759df-(int ptr(varptr(src))[0] shr 1)
  src=float ptr(varptr(i))[0]
  src:*(1.5-(x2*src*src))
  return 1/src
endfunction

Holzchopf

Meisterpacker

BeitragSo, Sep 06, 2015 13:17
Antworten mit Zitat
Benutzer-Profile anzeigen
~VERSCHOBEN~
Dieser Thread passte nicht in das Forum, in dem er ursprünglich gepostet wurde.

Normalerweise würde ich ja vorschlagen, den Code zu kommentieren - aber in diesem Fall reicht eigentlich die Quellenangabe. Der Originalcode ist auch nicht sonderlich hübsch kommentiert.

mfG
Holzchopf
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm
 

Matthias

BeitragMo, Sep 07, 2015 12:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo.

Habe schon lange nach einer schnellen Berechnung der Queadratwurzel gesucht. Laughing

Mir würde auch interessieren um wie viel schneller die Berechnung im Gegensatz zur herkömmlichen ist.

Mfg Matz
 

sinjin

BeitragDo, Sep 10, 2015 3:21
Antworten mit Zitat
Benutzer-Profile anzeigen
Steht alles auf der Wiki-Seite. Ungefähr 4x.

DAK

BeitragDo, Sep 10, 2015 13:10
Antworten mit Zitat
Benutzer-Profile anzeigen
Jein.

Es gibt zwei Gründe, warum der fast inverse square root schneller ist, als die normale Berechnung. Erstens, es benötigt keine Float-Berechnungen, die auf alten Geräten ohne FPU langsam waren. Zweitens, man muss nicht dividieren um auf 1/sqr(x) zu kommen, was das tatsächliche Ziel des Ganzen ist.

Der erste Grund hat sich lange erledigt. Jeder Prozessor (also für Computer und Handies verwende Prozessoren sind hier gemeint) aus diesem Jahrtausend hat eine FPU, da sind dann Float-Berechnungen nicht langsamer als Int-Berechnungen.

Den zweiten Grund machst du mit deiner Methode zunichte, indem du am Ende wieder dividierst.

Dazu kommt, dass du hier nicht in Assembler oder C programmierst, und damit noch einen Haufen Overhead dazu kommt, z.B. durch den Funktionsaufruf.

Ich hab deswegen mal einen Geschwindigkeitstest gemacht:

BlitzMax: [AUSKLAPPEN]
Framework BRL.StandardIO
Import BRL.Math

startTime = MilliSecs()
r#=0.0
For f# = 0 To 10000000
r# =+ Sqr(f#)
Next
Print("Normal: "+(MilliSecs()-startTime))

startTime = MilliSecs()
For f# = 0 To 10000000
r# =+ qsqr(f#)
Next
Print("Fast: "+(MilliSecs()-startTime))

startTime = MilliSecs()
For f# = 0 To 10000000
Local x2#=f#*0.5
Local i%=$5f3759df-(Int Ptr(Varptr(f#))[0] Shr 1)
src#=Float Ptr(Varptr(i))[0]
src#:*(1.5-(x2*src#*src#))
r# =+ 1/src#
Next
Print("Fast Direct: "+(MilliSecs()-startTime))


Print(r#) 'Noetig um zu verhindern, dass die Berechnung wegoptimiert wird

Function qsqr#(src#)
Local x2#=src*0.5
Local i%=$5f3759df-(Int Ptr(Varptr(src))[0] Shr 1)
src=Float Ptr(Varptr(i))[0]
src:*(1.5-(x2*src*src))
Return 1/src
EndFunction


Das Resultat ist Folgendes:

Code: [AUSKLAPPEN]
Normal: 44
Fast: 346
Fast Direct: 124


Das heißt, sqr() ist fast 8 mal schneller als qsqr(). Ruft man den Inhalt von qsqr() direkt auf, also ohne einen Funktionsaufruf darum, dann ist es nur mehr sqr() nur mehr 3x so schnell.


Verändert man den Code so, dass nicht die Wurzel sondern die inverse Wurzel berechnet wird, wie es in dem Algo sein sollte, dann kriegt man Folgendes als Ergebnis:

Code: [AUSKLAPPEN]
Normal: 94
Fast: 292
Fast Direct: 127


Das heißt, dank FPU ist 1/sqr(x) immer noch 3x schneller als iqsgr(x) und immer noch 30% schneller als wenn der Code ohne Funktion aufgerufen wird.
Gewinner der 6. und der 68. BlitzCodeCompo

Xeres

Moderator

BeitragDo, Sep 10, 2015 22:11
Antworten mit Zitat
Benutzer-Profile anzeigen
Results may vary.
Code: [AUSKLAPPEN]
Normal: 260
Fast: 159
Fast Direct: 150
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
T
HERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Thunder

BeitragDo, Sep 10, 2015 23:30
Antworten mit Zitat
Benutzer-Profile anzeigen
Habe mal ein altes Notebook ausgegraben und DAK's Beispiel noch erweitert.
Ich habe eine Funktion in Assembler hinzugefügt, die den SSE-Befehl SQRTSS verwendet:

Code: [AUSKLAPPEN]
Normal: 591
Fast: 495
Fast Direct: 308
SSE: 220

(getestet auf einem Intel Celeron-M mit 1,3 GHz)

BlitzMax: [AUSKLAPPEN]
Framework BRL.StandardIO
Import BRL.Math
Import "sse_sqrt.s"

Extern
Function sqrt_ss#(f#)
EndExtern

startTime = MilliSecs()
r#=0.0
For f# = 0 To 10000000
r# :+ Sqr(f#)
Next
Print("Normal: "+(MilliSecs()-startTime))

startTime = MilliSecs()
For f# = 0 To 10000000
r# :+ qsqr(f#)
Next
Print("Fast: "+(MilliSecs()-startTime))

startTime = MilliSecs()
For f# = 0 To 10000000
Local x2#=f#*0.5
Local i%=$5f3759df-(Int Ptr(Varptr(f#))[0] Shr 1)
src#=Float Ptr(Varptr(i))[0]
src#:*(1.5-(x2*src#*src#))
r# :+ 1/src#
Next
Print("Fast Direct: "+(MilliSecs()-startTime))

startTime = MilliSecs()
For f# = 0 To 10000000
r :+ sqrt_ss(f)
Next
Print("SSE: "+(MilliSecs()-startTime))

Print(r#) 'Noetig um zu verhindern, dass die Berechnung wegoptimiert wird

Function qsqr#(src#)
Local x2#=src*0.5
Local i%=$5f3759df-(Int Ptr(Varptr(src))[0] Shr 1)
src=Float Ptr(Varptr(i))[0]
src:*(1.5-(x2*src*src))
Return 1/src
EndFunction


Assemblerdatei sse_sqrt.s:
Code: [AUSKLAPPEN]
; Linux & Mac
format ELF

; Windows:
; format MS COFF

public sqrt_ss
sqrt_ss:
   sqrtss xmm1, dword [esp+4]
   push eax
   movss [esp], xmm1
   fld dword [esp]
   pop eax
ret
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit
  • Zuletzt bearbeitet von Thunder am Mo, Sep 14, 2015 1:07, insgesamt einmal bearbeitet

Lord Stweccys

BeitragSo, Sep 13, 2015 22:49
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]
Normal: 88
Fast: 114
Fast Direct: 89
SSE: 53

DAK

BeitragSo, Sep 13, 2015 23:57
Antworten mit Zitat
Benutzer-Profile anzeigen
Interessant, das die Werte scheinbar so stark variieren. Worum es mir hauptsächlich ging, war zu sagen, dass 4x so schnell als fixer Wert nicht passt.

Was für CPUs habt ihr? Ich habe hier einen i7-3626QM @ 2.2 GHz.
Gewinner der 6. und der 68. BlitzCodeCompo
 

sinjin

BeitragDi, Sep 15, 2015 16:43
Antworten mit Zitat
Benutzer-Profile anzeigen
Code: [AUSKLAPPEN]
Normal: 125
Fast: 113
Fast Direct: 78
SSE: 60

Habe einen I5 @ 2.67 GHz.

Cool Thunder, habe schon sämtlichen Code mit der SSE-Routine ausgetauscht.

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group