| Autor |
Beitrag |
minnime
  
Beiträge: 171
Win 7
Delphi Prism 2011, C# (VS 2010)
|
Verfasst: Fr 16.05.08 19:42
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.
Einloggen, um Attachments anzusehen!
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 18.05.08 00:05
Für wiederholte Anwendung der geometrischen Addition kann man aber auch:
Z := sqrt(a^2+b^2+c^2+d^2+...+n^2) nehmen.
Kannst Du da Vergleiche ziehen?
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Horst_H
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: So 18.05.08 18:30
Hallo,
wenn schon mit single gerechnet wird dann kann man den Faktor ja anpassen.
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;
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 www.ddj.com/184404202 statt 70 mit der FPU www.emboss.co.nz/pentopt/opcode_f.html )
Gruss Horst
|
|
minnime 
Beiträge: 171
Win 7
Delphi Prism 2011, C# (VS 2010)
|
Verfasst: Fr 23.05.08 19: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.
|
|
|
