Seite 1 von 1

2x cross versus 2x dot product

Verfasst: 11. Dez 2008 13:03
von Red*Star
Hallo, da ich nicht weiß wo es sonst reinpasst:

Ich lese immer immer wieder, z.B. auch hier - http://softsurfer.com/Archive/algorithm ... t-Triangle -, dass es aus Performancegründen Sinn macht ein doppeltes Kreuzprodukt gemäß der BAC-CAB-Regel durch zwei Skalarprodukte zu ersetzen:

\(\vec{a}\times(\vec{b}\times\vec{c}) = \vec{b}\,(\vec{a}\cdot\vec{c})-\vec{c}\,(\vec{a}\cdot\vec{b})\,\)

Wenn ich mich aber nun nicht verrechnet habe, dann hat die cross-cross-Variante auf der CPU 18 Flops (6 Additionen, 12 Multiplikationen), während die andere (empfohlene!) Variante 19 Flops (7 Additionen, 12 Multiplikationen) verbrät.

Hm. Hat dazu schon mal jemand was gelesen? Gibt es noch einen versteckten Grund, warum der Einsatz der Regel Sinn macht (auf der CPU, wohlgemerkt, sofern man spezialisierte Hardware hat, z.B. eine GPU, kommen ja eh wieder zusätzliche Faktoren ins Spiel)?

Anderenfalls:
Nimmt man die Erfahrungen von einigen "großen" ;) Computerwissenschaftlern hinzu - "Premature optimization is the root of all evil." oder "The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet." *) -, dann stellt sich mir die Frage, ob die Leute, die obige Regel empfehlen, nicht vielleicht einfach nur Angst vor dem Kreuzprodukt haben ;), oder zumindest ohne zu denken einfach irgendwas nachplappern, was sie mal wo gehört haben, was aber eigentlich gar nichts bringt, sondern nur den Quellcode unverständlicher macht.


*) Zitate von http://en.wikipedia.org/wiki/Optimizati ... ce)#Quotes

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 15:46
von MisterD123
liegt an der paralellisierbarkeit würd ich sagen, das rechte kannst du in drei schritten ausrechnen (beide werte in den klammern multiplizieren, beide werte außerhalb der klammer multiplizieren, subtraktion) während du links vier schritte brauchst (pro kreuzproduktrechnung einmal: multiplizieren (a1*b2 und a2*b1 zB) und die ergebnisse dann subtrahieren)

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 16:15
von Red*Star
Aber auf einer Single-Core-CPU klappt das mit dem Parallelisieren schlecht, oder? Na gut, es gibt da ja noch diese MMX extensions seit dem Pentium, und bestimmt auch sonst noch ganz viele tolle Chipsatz-Features... (für solche Hardwaresachen hab ich mich bislang nie sonderlich interessiert) - dann müsste man allerdings einen Compiler haben, der genau solche Optimierungen durchführt, damit das mit der BACCAB-Sache Sinn macht.

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 18:08
von MisterD123
letzendlich führt ja aber doch der renderer, in dem fall deine grafikkarte, die rechnung durch, und das ist dann nunmal hardware ;) renderer die in software rechnen sind normalerweise für einzelbilder, und da ist dann auch nicht mehr jedes einzelne gesparte befehl gold wert.

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 18:30
von Red*Star
Hehe, naja, wir machen gerade Raytracing in GDVI, und in dem Zusammenhang ist bei mir auch die Frage aufgetaucht ;)

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 20:35
von Render
Soweit ich das auf der verlinkten Seite verstehe wird dort das zweifach Kreuzprodukt durch das zweifach Skalarprodukt ersetzt um die Berechnung von s und t umformen zu können und dort einige Multiplikationen zu sparen weil viele Skalarprodukte mehrfach auftauchen.

Re: 2x cross versus 2x dot product

Verfasst: 11. Dez 2008 22:08
von ykaerflila
Die empfohlene Variante könnte beim PIPELINING schneller sein - auch auf Single-Core-CPUs. Geprüft habe ich es aber nicht :-)

Re: 2x cross versus 2x dot product

Verfasst: 12. Dez 2008 00:34
von Red*Star
Okay, genug Faktoren um mit dem Problem eine ganze Bachelorarbeit zu füllen... ich glaube ich *teste* es einfach mal, wenn ich Zeit hab. Empirisch. :D