Seite 1 von 3

Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 21:28
von c4s
Ich bin kein Mathematikexperte, deswegen frage ich einfach mal: Gibt es eine Geschwindigkeitsoptimierung (an ASM-Code bin ich nicht interessiert ;-)) für folgendes?

Code: Alles auswählen

PX = X - Radius : PY = Y - Radius
PF.f = Sqr(PX * PX + PY * PY) / Radius
Ich verwende es in einem CustomFilterCallback(), deswegen sollte es möglichst schnell sein.

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 21:33
von NicTheQuick
Es kommt drauf an, was du mit PF machen willst. Wenn es nur für einen Vergleich gedacht ist, sollte auch folgendes gehen:

Code: Alles auswählen

PF.f = (PX * PX + PY * PY) / (Radius * Radius)

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 21:53
von gnasen
Ich habe das noch nie ausprobiert, was geschwindigkeit angeht, aber du könntest die Wurzel zB mit der Taylorentwicklung beliebig nah approximieren. Insbesondere könntest du dann weniger genau rechnen (weniger Terme in der Summe) und dafür geschwindigkeit gewinnen.
Ich würde aber vermuten, dass die Wurzelfunktion schon ziemlich optimiert sein wird. Aber ausprobieren würde ich es evtl trotzdem mal. Wenn zB genauigkeit auf 1 oder 2 kommastellen reicht, evtl durchaus eine alternative.

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 21:58
von STARGÅTE
Wenn wir schon bei Taylor sind:
Taylorentwicklung kannst du vergessen, hab ich schon probiert.

Am Punkt wo es "spannend" wird, nämlich um 0.0, kannst du nicht entwickeln, weil du dann dauernt durch 0 teilen müsstest.
Entwickelt man um einen anderen Punkt, zb 1.0, wird die Funktion um 0.0 so ungenau, dass man zu viele Ordnungen braucht.

Um Sqr() kommt man leider nicht herum, wenn man wirklich das Ergebnis braucht.
Ansonsten wie NicTheQuick schrieb, wenn man nur wissen will ob "etwas im Kreis ist oder nicht" reicht der Vergleich zwischen den Quadraten

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 22:45
von gnasen
Ich habe mal gerade das Newtonverfahren ausgetestet, aber keine Chance. Selbst bei kleinsten For Next Schleifen in denen Additiert und Dividiert wird ist die Methode im Speedtest Meilenweit hinterher. Ich habe das Gefühl, das ist Chiptechnisch schon optimiert und kann mit software lösungen nicht annähernd eingeholt werden.
Angewandte Mathematik ist eh widerlich :lol:

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 29.07.2011 22:56
von c4s
Danke für die Tipps. Dann werde ich es wohl dabei belassen.

Das einzige was mir gerade noch eingefallen ist, ist natürlich die Ergebnisse Zwischenzuspeichern... Ich werde es demnächst mal testen, ob das überhaupt sinnvoll ist, d.h. einen entscheidenden Geschwindigkeitsvorteil bringt.

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 30.07.2011 14:46
von GPI
Für was brauchst du das genau?

Entfernung messen, ob eine Kollision da ist? Sieht fast so aus. Schon mal überlegt, in einen ersten schritt nicht in einen Kreis zu testen, sondern auf "boxen". Erst wenn beide Punkte in X und Y-Richtung weniger als 100 Pixel entfernt sind, dann die richtige Kontrolle durchzuführen. Dann erstellst du ein Arry mit 100x100-Elementen mit den richtigen Wert und fertig :)

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 30.07.2011 15:10
von c4s
@GPI
Wie gesagt, ich verwende es in einem CustomFilterCallback(), um die Farbe vom Abstand zur Mitte abhängig zu machen.

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 30.07.2011 15:23
von Thorium
Jenachdem was du genau machen willst, könntest du jede Menge Geschwindigkeit rausholen, wenn du auf CustomFilterCallback verzichtest und die stattdessen den Pointer aufs Bild besorgst und selbst im Speicher rummalst.
So hast du pro Pixel ein Call und Calls sind Performancefresser.

Re: Optimierung für Sqr(a²+b²) ?

Verfasst: 30.07.2011 15:32
von STARGÅTE
@Thorium
Im vergleich zu den Berechungen selbst, ist das aufrufen eins Calls sehr schnell.
Das selber rummalem mit Pointer bringt keinen Vorteil, weil die Berechnungen bleiben.