Entwickler-Ecke :: Thema anzeigen - alternativer Algorithmus zur geometrischen Addition

minnime - Fr 16.05.08 18:42
Titel: alternativer Algorithmus zur geometrischen Addition

Ich habe einen neuen Algorithmus kennengelernt, mit dem geometrische Additionen schneller durchgeführt werden können.

Normalerweise wird eine geometrische Addition mit folgender Formel durchgeführt: c = √(a^2 + b^2)
Dabei werden schon mal zwei Multiplikationen und eine Addition benötigt, dazu noch die Wurzel die geradezu unendlich aufwändig und der wohl überhaupt langsamste Operator ist.

Das alternative Verfahren sieht folgendermaßen aus: c = G + k/2 G: größerer Operand k: kleinerer Operand
Das heißt man muss vorher die beiden Operanden nach ihrer numerischen größe vergleichen.

Hierbei also nur noch eine Addition, eine Division, ein Vergleich und evtl. drei Wertzuweisungen benötigt. Nach meinen Messungen weist dieses Verfahren die zwanzig- bis dreißigfache Geschwindigkeit des herkömmlichen Verfahrens auf, weicht aber auch bis zu 15% vom korrekten Wert ab, wobei die Abweichung immer größer als der richtige Wert ist. Der Einsatzbereich dürfte überall dort liegen wo es schnell aber nicht so genau sein muss z.B. in Computerspielen für Entfernungsbestimmungen der KI, teilen der Physikberechnung oder auch in DSPs um D/A- Umwandlungen vorzubereiten. Ich selbst kenne das Verfahren aus letztgenanntem Bereich.

Ich habe noch ein kleines Programm angehängt mit dem man Geschwindigkeit und Genauigkeit schnell mal selbst testen kann. Es handelt sich um eine Kommandozeilenapplikation und ist mit Chrome geschrieben. Die Source ist zwar nicht dokumentiert aber als Übersicht dürfte es reichen.

Horst_H - So 18.05.08 17:30

Hallo,

wenn schon mit single gerechnet wird dann kann man den Faktor ja anpassen.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

program nonsens;

{$APPTYPE CONSOLE}

 var
   x,y,i  : integer;
   a,b,f1,f2,maxdiff,diff,fakt :double;
 begin
  fakt := 0.339246;
  maxdiff := 1.0;
  For x := 1 to 1000 do
    For y := x to 1000 do
      begin
      a:= x;
      b:= y;{a immer kleiner b}
      f1 := sqrt(sqr(a)+sqr(b));
      f2 := b + a * fakt;
      diff := f2/f1;
      if diff < 1 then
        diff := 1/diff;
      if diff > maxdiff then
         begin
         maxdiff := diff;
         writeln(x:10,y:10,maxdiff:16:8);
         end
       end;
end.
Ergibt
PMODE/W DOS Extender v1.33
Copyright (C) 1994-1997, Charles Scheffold and Thomas Pytel
         1         1      1.05597744

Damit ist die relative Abweichung kleiner als 5,6%
und ueberhaupt bei single kann man mit 3dNow sowas wie sqrt in ein paar Takten berechnen (Wurzel in 8 Takten http://www.ddj.com/184404202 statt 70 mit der FPU http://www.emboss.co.nz/pentopt/opcode_f.html )

Gruss Horst

minnime - Fr 23.05.08 18:52

Wie man dieses Verfahren mit mehreren Operanden einsetzt weiß ich nicht. Bin da auch kein Experte, ich hab das auch einfach nur übernommen. Ich würde einfach das alternative Verfahren mehrfach anwenden, wodurch es im Vergleich an Effizienz verliert. Dennoch liegt der große Vorteil schließlich in der Reduzierung der Wurzel, die auch mit 8 Takten noch viel Zeit schluckt. Single habe ich nur aus Gewohnheit genommen, ist auch glaube ich nicht so ausschlaggebend. Die Genauigkeit des Verfahrens ist von der Differenz der beiden Operanden abhängig d.h es hängt mit dem Quotienten 2 zusammen. Wenn man den Quotienten für jede Aufgabenstellung entsprechend anpasst müsste sich die Genauigkeit beliebig erhöhen lassen. Ich werde mir das bei Gelegenheit nocheinmal ansehen.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2026 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!