#1 19.10.2008 21:41:27

Carsten
ProMember
Ort: Braunschweig
Registriert: 05.01.2006
Beiträge: 220
Web-Seite

Schnelle Winkelfunktionen gesucht?

Hat jemand eine schnelle (also auf Tabelle beruhende) Funktion für die gängigen Winkelfunktionen zur Hand?
Mega-genau muß es nicht unbedingt sein.

Carsten

Offline

 

#2 20.10.2008 05:04:38

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Schnelle Winkelfunktionen gesucht?

Ich verstehe die Frage nicht so ganz.

Du nimmst dir einfach je ein Feld und fuellst dieses mit den Werten der Winkelfunktion. Dabei hast du entsprechend so viele Einträge, wie du gerne an Genauigkeit hättest.
Und dann schreibst du dir nur 3 kleine Funktionen, die an der richtigen Stelle nachsehen.

Offline

 

#3 20.10.2008 08:22:12

Carsten
ProMember
Ort: Braunschweig
Registriert: 05.01.2006
Beiträge: 220
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Klar. Aber ich dachte sowas gibt's vielleicht fertig - muß man ja nicht alles neu erfinden.

Carsten

Offline

 

#4 20.10.2008 13:07:14

Gnietschow
ProMember
Ort: Berlin
Registriert: 20.06.2007
Beiträge: 237

Re: Schnelle Winkelfunktionen gesucht?

Ist denn so etwas wirklich schneller und bringt dieser relativ geringe Geschwindigkeitsvorteil was? Ich hatte mal genau das geschrieben, indem ich ein Array[0..359] mit Sinuswerten gefüllt hatte und dann per Gettickcount die Geschwindigkeiten verglichen habe. Da war Sin() immer schneller als meine Funktion. Und sobald ich zwischendurch DegToRad verwendet hatte, war eh alles im Eimer da diese Verhältnismäßig lahm ist.

Gnietschow


Es gibt 10 Gruppen von Menschen - die die das Binärsystem verstehen und die anderen.  :-)
Vegetarier essen meinem Essen das Essen weg ;)
-------------------------------------------------------------------------------------------------------------------
Der Community-Hub für Videospiele: gameloop.io

Offline

 

#5 20.10.2008 13:53:21

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Ich würde auch sagen, dass sowas nicht wirklich schneller ist. Ein Problem schneller zu lösen in dem man Speicher drauf wirft ist nur selten eine gute Lösung. Schließlich muss das Array entweder im Cache liegen (und der Platz kann nicht anderweitig genutzt werden) oder es ist ein Zugriff auf den Hauptspeicher erforderlich, was sicher langsamer ist als den Sinus auszurechnen.
Normalerweise sind die Implementierungen in Standardbibliotheken immer besser als man das mit akzeptablen Aufwand selbst umsetzen kann. Insbesondere weil z.B. Prozessorerweiterungen genutzt werden, etc.

Es macht viel mehr Sinn zu überlegen ob man den wirklich die Winkelfunktion überhaupt benötigt.


My software never has bugs. It just develops random features.

Offline

 

#6 20.10.2008 14:47:45

Carsten
ProMember
Ort: Braunschweig
Registriert: 05.01.2006
Beiträge: 220
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Ich dachte vor allem an arctan2. Gilt das für die auch? Die rufe ich einige 1000x pro Frame auf, so daß sich Einsparung schon bemerkbar machen könnte.

Carsten

Offline

 

#7 20.10.2008 14:51:44

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Das gilt für jede Funktion, aber du kannst es natürlich einfach mal ausprobieren. Kann aber auch auf verschiedenen Rechnern zu verschiedenen Ergebnissen führen.


My software never has bugs. It just develops random features.

Offline

 

#8 20.10.2008 15:59:56

Lotipats
UltraMember
Registriert: 17.05.2005
Beiträge: 395

Re: Schnelle Winkelfunktionen gesucht?

Ich habe hier mal ein kleines Beispiel geschrieben. Und ja, ihr seht richtig. Ich habe 10Mio. mal rechnen lassen, um die Unterschiede sichtbar zu machen. Bei 100.000 waren wir bei 0ms gegen 0ms. wink

Das Ergebnis war:

Code:

Zeit-Sinus-Nachsehen: 297ms
Zeit-Sinus-Normal: 250ms
Zeit-ACos-Nachsehen: 296ms
Zeit-ACos-Normal: 422ms

Daran sieht man, dass es sich fuer den Sinus nicht lohnt, fuer ArcCos aber schon eher. Aber der Rahmen muss auch beachtet werden. Für 5 oder 10 Mal im Frame lohnt sich das nicht.
Bei ArcTan2 würde es sich vermutlich auch lohnen, einfach mal testen. wink

Hier der Quelltext:

Code: delphi

program project1;

{$APPTYPE CONSOLE}

uses
  sysutils, math,windows;

const
  genauigkeit=1000;
  anzel=genauigkeit*2+1;
  anzel2=10000000;
var
  sin1:array [0..(anzel-1)]of real;
  acos:array [0..(anzel-1)]of real;
  rand:array [0..(anzel2-1)]of real;
  rand2:array [0..(anzel2-1)]of real;
  i:integer;
  t:cardinal;
  zw:real;
function lookupsin(val:real):real;
begin
  if(val<0)or(val>2*pi)then result:=0
  else result:=sin1[trunc(val*genauigkeit)];
end;

function lookuparccos(val:real):real;
begin
  if(val<-1.0)or(val>1.0)then result:=0
  else result:=acos[trunc(val*genauigkeit+genauigkeit)];
end;

begin
  //erstmal die Tabellen erstellen
  randomize();
  i:=0;
  while(i<anzel)do
  begin
    sin1[i]:=sin(pi*2*(i)/genauigkeit);
    acos[i]:=arccos((i-genauigkeit)/genauigkeit);
    inc(i);
  end;
  i:=0;
  while(i<anzel)do
  begin
    rand[i]:=random()*2*pi;
    rand2[i]:=random()*2-1.0;
    inc(i);
  end;

  //Und Zeitmessung fuer Nachsehen Sinus
  t:=gettickcount();
  i:=0;
  while(i<anzel2)do
  begin
    zw:=lookupsin(rand[i]);
    inc(i);
  end;
  writeln('Zeit-Sinus-Nachsehen: '+inttostr(gettickcount()-t)+'ms');

  //Und Zeitmessung fuer Nachsehen Sinus
  t:=gettickcount();
  i:=0;
  while(i<anzel2)do
  begin
    zw:=sin(rand[i]);
    inc(i);
  end;
  writeln('Zeit-Sinus-Normal: '+inttostr(gettickcount()-t)+'ms');

  //Und Zeitmessung fuer Nachsehen ArcCos
  t:=gettickcount();
  i:=0;
  while(i<anzel2)do
  begin
    zw:=lookuparccos(rand2[i]);
    inc(i);
  end;
  writeln('Zeit-ACos-Nachsehen: '+inttostr(gettickcount()-t)+'ms');

  //Und Zeitmessung fuer ArcCos
  t:=gettickcount();
  i:=0;
  while(i<anzel2)do
  begin
    zw:=arccos(rand2[i]);
    inc(i);
  end;
  writeln('Zeit-ACos-Normal: '+inttostr(gettickcount()-t)+'ms');

  write('beenden...');
  readln;
end.

Offline

 

#9 20.10.2008 20:20:39

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

@Lotipats: Es ist möglich das in deinem Versuch das Array schneller ist, weil du nichts anderes tust. Das Array (bzw. die Arrays) kann die ganze Zeit im Cache bleiben. Allerdings sind 15 kb auch jetzt nicht sooo viel.

Zitat:

Bei 100.000 waren wir bei 0ms gegen 0ms.

Er will das 1000 mal pro Frame nutzen....bei 50 Frames pro Sekunde....


My software never has bugs. It just develops random features.

Offline

 

#10 21.10.2008 18:16:31

Carsten
ProMember
Ort: Braunschweig
Registriert: 05.01.2006
Beiträge: 220
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Schnell mal "besten Dank". Werde mich frühestens morgen Abend damit befassen können. Würdet Ihr beim atan2 ein 2-dimensionales Array für x und y nehmen?

Carsten

Offline

 

#11 21.10.2008 18:36:23

Coolcat
ProGuru
Ort: Aachen, NRW
Registriert: 24.01.2005
Beiträge: 2780
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

Zitat:

Würdet Ihr beim atan2 ein 2-dimensionales Array für x und y nehmen?

Ganz sicher nicht. Wenn du da auch 1000 mal 1000 Werte nimmst und als Datentyp ein 8 Byte Double  (bzw. Real) hast du schon 7,6 MB!! Ein Cache hat normal so 1 MB (*) und wird ja normal nicht nur dafür genutzt. Alleine das Betriebssystem braucht ja schon mal was davon.... du wirst also meistens auf den Hauptspeicher warten müssen! Insbesondere der Hauptspeicher bei Intel CPUs ist langsam, da der Speichercontroller nicht wie bei AMD in die CPU integriert ist. Dafür hat Intel allerdings meist größere Caches.

Etwas googlen ergab das man atan2 so implementieren kann (ohne Gewähr):

Code:

function atan2 (y, x : real) : real;
begin
  if x > 0       then  atan2 := arctan (y/x)
  else if x < 0  then  atan2 := arctan (y/x) + pi
  else                 atan2 := pi/2 * sgn (y);
end;

Du solltest also allerhöchstens den arctan speichern. Ich würde gar nichts speichern, sondern alles berechnen.

(*) bei neueren Systemen wahrscheinlich mittlerweile mehr. http://de.wikipedia.org/wiki/Cache#Prozessor-Cache: "Gängige Größen für L1-Caches sind 4 bis 256 KB und für den L2 64 bis 12288 KB." Dabei darf man nicht vergessen das der Cache ggf. von mehreren Cores gemeinsam genutzt wird.


My software never has bugs. It just develops random features.

Offline

 

#12 27.10.2008 08:57:11

Carsten
ProMember
Ort: Braunschweig
Registriert: 05.01.2006
Beiträge: 220
Web-Seite

Re: Schnelle Winkelfunktionen gesucht?

So - habe mal etwas getestet und das ganze auf arctan2 erweitert. Beim arctan ist das Problem, daß der Wertebereich nicht auf -1...1 beschränkt ist. arctan(v) ist aber das gleiche wie arcsin(v/sqrt(1+v*v)), so daß man den arctan in eine arcsin-Funktion überführen kann. Passend ungeformt und angepaßt an alle 4 Quadranten ergibt sich arctan2 so:

Code:

function arctan2_schnell(y, x:single):single;
begin
  if x > 0       then  result :=  arcsin_schnell(y/(sqrt(sqr(x)+sqr(y))))
  else if x < 0  then  result := -arcsin_schnell(y/(sqrt(sqr(x)+sqr(y)))) + pi
  else                 result :=  pi/2 * Sign (y);
end;

Das ist immer noch mindestens doppelt so schnell wie arctan2. Unter realen Bedingungen an einer besonders kritischen Stelle (sehr viele Objekte in der Umgebung) machte das einen Sprung von 38 auf 40 fps aus - immerhin "schnell verdiente" 2 fps.

Carsten

Offline

 

Brett Fußzeile

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson