Fast inverse square root

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	sinjin Betreff: Fast inverse square root	Sa, Sep 05, 2015 23:37 Antworten mit Zitat
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] [EINKLAPPEN] function qsqr#(src#) local x2#=src0.5 local i%=$5f3759df-(int ptr(varptr(src))[0] shr 1) src=float ptr(varptr(i))[0] src:(1.5-(x2srcsrc)) return 1/src endfunction

sinjin

Betreff: Fast inverse square root

Sa, Sep 05, 2015 23:37
Antworten mit Zitat

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	So, Sep 06, 2015 13:17 Antworten mit Zitat
~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 BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018) Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Holzchopf

Meisterpacker

So, Sep 06, 2015 13:17
Antworten mit Zitat

~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 BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

	Matthias	Mo, Sep 07, 2015 12:51 Antworten mit Zitat
Hallo. Habe schon lange nach einer schnellen Berechnung der Queadratwurzel gesucht. Mir würde auch interessieren um wie viel schneller die Berechnung im Gegensatz zur herkömmlichen ist. Mfg Matz

Matthias

Mo, Sep 07, 2015 12:51
Antworten mit Zitat

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	Do, Sep 10, 2015 3:21 Antworten mit Zitat
Steht alles auf der Wiki-Seite. Ungefähr 4x.

sinjin

Do, Sep 10, 2015 3:21
Antworten mit Zitat

Steht alles auf der Wiki-Seite. Ungefähr 4x.

	DAK	Do, Sep 10, 2015 13:10 Antworten mit Zitat
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] [EINKLAPPEN] 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-(x2src#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#=src0.5 Local i%=$5f3759df-(Int Ptr(Varptr(src))[0] Shr 1) src=Float Ptr(Varptr(i))[0] src:(1.5-(x2srcsrc)) Return 1/src EndFunction Das Resultat ist Folgendes: Code: [AUSKLAPPEN] [EINKLAPPEN] 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] [EINKLAPPEN] 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

DAK

Do, Sep 10, 2015 13:10
Antworten mit Zitat

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	Do, Sep 10, 2015 22:11 Antworten mit Zitat
Results may vary. Code: [AUSKLAPPEN] [EINKLAPPEN] 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 THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

Xeres

Moderator

Do, Sep 10, 2015 22:11
Antworten mit Zitat

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
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)

	Thunder	Do, Sep 10, 2015 23:30 Antworten mit Zitat
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] [EINKLAPPEN] Normal: 591 Fast: 495 Fast Direct: 308 SSE: 220 (getestet auf einem Intel Celeron-M mit 1,3 GHz) BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] 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-(x2src#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#=src0.5 Local i%=$5f3759df-(Int Ptr(Varptr(src))[0] Shr 1) src=Float Ptr(Varptr(i))[0] src:(1.5-(x2srcsrc)) Return 1/src EndFunction Assemblerdatei sse_sqrt.s: Code: [AUSKLAPPEN] [EINKLAPPEN] ; 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

Thunder

Do, Sep 10, 2015 23:30
Antworten mit Zitat

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	So, Sep 13, 2015 22:49 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] Normal: 88 Fast: 114 Fast Direct: 89 SSE: 53

Lord Stweccys

So, Sep 13, 2015 22:49
Antworten mit Zitat

Code: [AUSKLAPPEN]

Normal: 88
Fast: 114
Fast Direct: 89
SSE: 53

	DAK	So, Sep 13, 2015 23:57 Antworten mit Zitat
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

DAK

So, Sep 13, 2015 23:57
Antworten mit Zitat

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	Di, Sep 15, 2015 16:43 Antworten mit Zitat
Code: [AUSKLAPPEN] [EINKLAPPEN] 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.

sinjin

Di, Sep 15, 2015 16:43
Antworten mit Zitat

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.

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

Nach Oben

BlitzBasic Portal

Fast inverse square root

Betreff: Fast inverse square root