Schnellere(?) Längenberechnung

Übersicht

BlitzMax, BlitzMax NG

Codearchiv & Module

	FireballFlame Betreff: Schnellere(?) Längenberechnung	Fr, Aug 26, 2016 22:23 Antworten mit Zitat
Wenn man die Entfernung zweier Punkte in der Ebene ausrechnen möchte, tut man das normalerweise indem man den Betrag des Vektors von einem der Punkte zum anderen ausrechnet, also nach dem Prinzip Code: [AUSKLAPPEN] [EINKLAPPEN] x = p1_x - p2_x y = p1_y - p2_y dist = Sqr(x * x + y * y) Solange man nur Entfernungen miteinander vergleichen möchte, kann man die hier langsamste Operation, die Wurzel, einfach weglassen. Benötigt man aber tatsächlich die Entfernung, ist die obige Formel mit einer selbstgeschriebenen Funktion schwer zu überbieten. Unter Umständen kann man aber auf Kosten eines genauen Ergebnisses doch noch etwas Geschwindigkeit herausholen: Die Idee ist von hier. Kurz erklärt: es werden für "Sqr(x * x + y * y)" zwei grobe Annäherungen berechnet. Die erste ist "Max(Abs(x), Abs(y))" und funktioniert prima, wenn x oder y sehr nahe an 0 liegt, bei ungefähr gleichgroßen Beträgen von x und y liegt sie aber gründlich daneben. Die zweite ist "(Abs(x) + Abs(y)) / Sqr(2)" und zeigt das umgekehrte Verhalten. Da beide Annäherungen immer einen Wert kleiner oder gleich der richtigen Lösung liefern, nimmt man nun das Maximum aus beiden. Zum Schluss kann man noch mit einem passenden Faktor (im Code unten "a" genannt) den Fehler gleichmäßig zwischen "zu groß" und "zu klein" verteilen. Er liegt dann bei ca. ±4%. Hier ist die eigentliche Funktion, geschrieben in C Code: [AUSKLAPPEN] [EINKLAPPEN] #include <math.h> inline int max_int (int x, int y) {return (x > y) ? x : y;} inline float max_float(float x, float y) {return (x > y) ? x : y;} float FastNorm(int x, int y) { const float invSqr2 = 0.707106781f; // Sqr(0.5) //const float a = 1.0f; // approximation <= real value //const float a = 1.08239220f; // Sqr(4 - 2 * Sqr(2)) // approximation >= real value const float a = 1.04119610f; // (Sqr(4 - 2 * Sqr(2)) + 1) / 2; // approximation ~= real value (max pos error = max neg error) x = abs(x); y = abs(y); const float metricMax = max_int(x, y); // good for x ~ 0 or y ~ 0 const float metricInvSqr2 = invSqr2 * (x + y); // good for x ~ y return a * max_float(metricMax, metricInvSqr2); // https://majewsky.wordpress.com/2011/04/10/optimization-tricks-fast-norm/ } und benutzt wird sie in BlitzMax mit einem entsprechenden Import und BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Extern "C" Function FastNorm:Float(x:Int, y:Int) End Extern Der Einsatz der Funktion lohnt sich wahrscheinlich aber nur unter optinalen Bedingungen. Hat man beispielsweise x und y von vornherein als Ints gegeben und speichert das Ergebnis in einer Float/Double-Variablen ab, ist sie in (meinem simplen Test) fast doppelt so schnell wie die Sqr-Standardformel. Speichert man das Ergebnis allerdings in einem Int, geht der Vorteil größtenteils verloren; hat man x und y als Gleitkommazahlen gegeben und muss sie bei jedem Aufruf erst casten, dreht sich das Verhältnis sogar um. Hier noch eine Visualisierung zur Genauigkeit des Ergebnisses: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Framework BRL.Max2D Import BRL.GlMax2D Import "fastnorm.c" Extern "C" Function FastNorm:Float(x:Int, y:Int) End Extern Graphics 1024, 768, 0, , GRAPHICS_BACKBUFFER SetOrigin 512, 384 Repeat Cls SetColor 128, 128, 128 DrawRect -512, 0, 1024, 1 DrawRect 0, -384, 1, 768 SetBlend AlphaBlend For Local a:Float = 0 Until 360 Step .5 Local x:Float = Cos(a) * 350 Local y:Float = Sin(a) * 350 Local fastdist:Float = FastNorm(x, y) Local x2:Float = Cos(a) * fastdist Local y2:Float = Sin(a) * fastdist SetAlpha 1 SetColor 255, 255, 255 Plot x, y SetColor 255, 0, 0 SetAlpha .5 DrawLine 0, 0, x2, y2 Next Flip Until AppTerminate() Or KeyHit(KEY_ESCAPE) EndGraphics Zu sehen ist ein Kreis aus weißen Punkten, rot eingezeichnet die von der Funktion aus diesen Punkten errechnete Distanz vom Mittelpunkt.
PC: Intel Core i7 @ 4x2.93GHz \| 6 GB RAM \| Nvidia GeForce GT 440 \| Desktop 2x1280x1024px \| Windows 7 Professional 64bit Laptop: Intel Core i7 @ 4x2.00GHz \| 8 GB RAM \| Nvidia GeForce GT 540M \| Desktop 1366x768px \| Windows 7 Home Premium 64bit

FireballFlame

Betreff: Schnellere(?) Längenberechnung

Fr, Aug 26, 2016 22:23
Antworten mit Zitat

Wenn man die Entfernung zweier Punkte in der Ebene ausrechnen möchte, tut man das normalerweise indem man den Betrag des Vektors von einem der Punkte zum anderen ausrechnet, also nach dem Prinzip Code: [AUSKLAPPEN]

x = p1_x - p2_x
y = p1_y - p2_y
dist = Sqr(x * x + y * y)

Solange man nur Entfernungen miteinander vergleichen möchte, kann man die hier langsamste Operation, die Wurzel, einfach weglassen. Benötigt man aber tatsächlich die Entfernung, ist die obige Formel mit einer selbstgeschriebenen Funktion schwer zu überbieten. Unter Umständen kann man aber auf Kosten eines genauen Ergebnisses doch noch etwas Geschwindigkeit herausholen:

Die Idee ist von hier. Kurz erklärt: es werden für "Sqr(x * x + y * y)" zwei grobe Annäherungen berechnet. Die erste ist "Max(Abs(x), Abs(y))" und funktioniert prima, wenn x oder y sehr nahe an 0 liegt, bei ungefähr gleichgroßen Beträgen von x und y liegt sie aber gründlich daneben. Die zweite ist "(Abs(x) + Abs(y)) / Sqr(2)" und zeigt das umgekehrte Verhalten. Da beide Annäherungen immer einen Wert kleiner oder gleich der richtigen Lösung liefern, nimmt man nun das Maximum aus beiden. Zum Schluss kann man noch mit einem passenden Faktor (im Code unten "a" genannt) den Fehler gleichmäßig zwischen "zu groß" und "zu klein" verteilen. Er liegt dann bei ca. ±4%.

Hier ist die eigentliche Funktion, geschrieben in C Code: [AUSKLAPPEN]

#include <math.h>

inline int max_int (int x, int y) {return (x > y) ? x : y;}
inline float max_float(float x, float y) {return (x > y) ? x : y;}

float FastNorm(int x, int y) {
const float invSqr2 = 0.707106781f; // Sqr(0.5)
//const float a = 1.0f;                         // approximation <= real value
//const float a = 1.08239220f; // Sqr(4 - 2 * Sqr(2))       // approximation >= real value
const float a = 1.04119610f; // (Sqr(4 - 2 * Sqr(2)) + 1) / 2; // approximation ~= real value (max pos error = max neg error)

x = abs(x);
y = abs(y);

const float metricMax = max_int(x, y);    // good for x ~ 0 or y ~ 0
const float metricInvSqr2 = invSqr2 * (x + y); // good for x ~ y

return a * max_float(metricMax, metricInvSqr2);
// https://majewsky.wordpress.com/2011/04/10/optimization-tricks-fast-norm/
}

und benutzt wird sie in BlitzMax mit einem entsprechenden Import und BlitzMax: [AUSKLAPPEN]

Extern "C"
	Function FastNorm:Float(x:Int, y:Int)
End Extern

Der Einsatz der Funktion lohnt sich wahrscheinlich aber nur unter optinalen Bedingungen. Hat man beispielsweise x und y von vornherein als Ints gegeben und speichert das Ergebnis in einer Float/Double-Variablen ab, ist sie in (meinem simplen Test) fast doppelt so schnell wie die Sqr-Standardformel. Speichert man das Ergebnis allerdings in einem Int, geht der Vorteil größtenteils verloren; hat man x und y als Gleitkommazahlen gegeben und muss sie bei jedem Aufruf erst casten, dreht sich das Verhältnis sogar um.

Hier noch eine Visualisierung zur Genauigkeit des Ergebnisses: BlitzMax: [AUSKLAPPEN]

SuperStrict
Framework BRL.Max2D
Import BRL.GlMax2D
Import "fastnorm.c"

Extern "C"
	Function FastNorm:Float(x:Int, y:Int)
End Extern



Graphics 1024, 768, 0, , GRAPHICS_BACKBUFFER
SetOrigin 512, 384

Repeat
	Cls
	SetColor 128, 128, 128
	DrawRect -512, 0, 1024, 1
	DrawRect 0, -384, 1, 768
	SetBlend AlphaBlend
	
	For Local a:Float = 0 Until 360 Step .5
		Local x:Float = Cos(a) * 350
		Local y:Float = Sin(a) * 350
		
		Local fastdist:Float = FastNorm(x, y)
		Local x2:Float = Cos(a) * fastdist
		Local y2:Float = Sin(a) * fastdist
		
		SetAlpha 1
		SetColor 255, 255, 255
		Plot x, y
		SetColor 255, 0, 0
		SetAlpha .5
		DrawLine 0, 0, x2, y2
		
	Next
	
	Flip
Until AppTerminate() Or KeyHit(KEY_ESCAPE)
EndGraphics

Zu sehen ist ein Kreis aus weißen Punkten, rot eingezeichnet die von der Funktion aus diesen Punkten errechnete Distanz vom Mittelpunkt.