Hallo zusammen, ich suche ein Compilertool, welches erlaubt eine komplexe Gleichung zu optimieren. Ich habe es in faktorisierter schreibweise, und ich hätte gerne ein Tool, das entsprechend ausklammert, sodass ich laufzeit spare. (Ich mache es akutuell per Hand, und das ist fehleranfällig.) Gibt es sowas? -Michael
Michael H. schrieb: > das entsprechend ausklammert, sodass ich laufzeit spare. Ueberlass das dem Compiler deiner Wahl. Der macht das sehr gut und prozessorspezifisch, was du haendisch kaum machst.
Für allgemeine Ausdrücke kann Mathematica das auch. Leider nicht ganz billig. Wolfram Alpha reicht vielleicht auch
leo schrieb: > Michael H. schrieb: >> das entsprechend ausklammert, sodass ich laufzeit spare. > > Ueberlass das dem Compiler deiner Wahl. Der macht das sehr gut und > prozessorspezifisch, was du haendisch kaum machst. Ganz viele Dinge kann der Compiler nicht optimieren weil das Ergebnis aus seiner Sicht nicht identisch ist aber mathematisch identisch ist. Simples Beispiel gefällig: https://godbolt.org/z/mdgHMp Matthias
Μαtthias W. schrieb: > nicht identisch ist aber mathematisch identisch ist. Ja, das gibt's. Aber dazu muss man auch wissen, ob das eine Rolle spielt, oder ob man durch Verbesserung des Algorithmus nicht viel mehr erzielen kann. Durch Pipelining werden solche Opcodeauswuechse gut versteckt. Hingegen kostet ein zusaetzlicher Speicherzugriff gleich mal ~100 Cyclen, wenn man Pech hat. Konkreten Code mit realen Daten ausmessen hilft. leo
Μαtthias W. schrieb: > Ganz viele Dinge kann der Compiler nicht optimieren weil das Ergebnis > aus seiner Sicht nicht identisch ist aber mathematisch identisch ist. > Simples Beispiel gefällig: Etwas genauer: Ganz viele Dinge darf der Compiler nicht optimieren, weil das Ergebnis mathematisch nicht identisch ist. Für den Compiler sind die Regeln der jeweiligen Programmiersprache relevant. In z.B. c gelten allerdings andere Regeln für floats, als die gewöhnlichen Regeln für Reelle Zahlen, die man in der Schule lernt.
Ich habe es jetzt mit Maple Gemacht. CodeGeneration[C](g5, optimize = true, precision = single) Das letzte bisschen (Potenzen rausschmeisen) muss man noch per Hand machen. Und nein, der Compiler kann das nicht optimieren, diese Gleichungen...
Μαtthias W. schrieb: > Ganz viele Dinge kann der Compiler nicht optimieren weil das Ergebnis > aus seiner Sicht nicht identisch ist aber mathematisch identisch ist. > Simples Beispiel gefällig: > > https://godbolt.org/z/mdgHMp > > Matthias Sollten die beiden Funktionen das gleiche Ergebnis liefern oder wird das überbewertet? ;-) Ändert zwar nix daran, dass das Horner-Schema schneller ist, aber so vergleicht man Äpfel mit Birnen... (-5 => +5)
Michael F. schrieb: > Μαtthias W. schrieb: >> Ganz viele Dinge kann der Compiler nicht optimieren weil das Ergebnis >> aus seiner Sicht nicht identisch ist aber mathematisch identisch ist. >> Simples Beispiel gefällig: >> >> https://godbolt.org/z/mdgHMp >> >> Matthias > > Sollten die beiden Funktionen das gleiche Ergebnis liefern oder wird das > überbewertet? ;-) > > Ändert zwar nix daran, dass das Horner-Schema schneller ist, aber so > vergleicht man Äpfel mit Birnen... > > (-5 => +5) Normalerweise geht Korrektheit vor Schnelligkeit. Und bei Korrektheit kommt es meistens auf die Reihenfolge der Operationen an. In der squareHorner Funktion des Beispiels wird der numerische Fehler von 2*x-4 3 weitere Male mit x multipliziert und kann damit sehr groß werden (Fehler * x**3). Wenn man dagegen eine numerisch sinnvolle square Funktion nimmt,
1 | auto square(unsigned int x) { |
2 | return 11 + 7*x + 5*pow(x,2) - 4*pow(x,3) + 2*pow(x,4); |
3 | }
|
wird der numerische Fehler von pow nur mit einer Konstanten multipliziert (Fehler * konst). Die Fortpflanzung durch Addition ist komplizierter, lässt sich aber für die square Funktion nicht wirklich vermeiden. Die beiden Funktionen sind auch ein gutes Beispiel dafür, dass der Compiler sowas optimiert, wenn er darf. Wenn man unsigned ints statt doubles verwendet und den +/-5 Fehler beseitigt, liefert der Compiler ein (nahezu) identisches Ergebnis. Für unsigned ints muss er nicht auf Overflows achten und kann die Operationen umsortieren wie er lustig ist, ohne dass sich etwas am Ergebnis ändern kann. Für signed ints darf er es nicht, da evtl. auftretende Overflows undefined behaviour sind. Für unsigned Datentypen anderer Größe machen die Promotion Regeln dem Compiler das Leben schwer.
mh schrieb: > In der squareHorner Funktion des Beispiels wird der numerische Fehler > von 2*x-4 3 weitere Male mit x multipliziert und kann damit sehr groß > werden (Fehler * x**3). Wenn man dagegen eine numerisch sinnvolle square > Funktion nimmt, >
1 | > auto square(unsigned int x) { |
2 | > return 11 + 7*x + 5*pow(x,2) - 4*pow(x,3) + 2*pow(x,4); |
3 | > } |
> wird der numerische Fehler von pow nur mit einer Konstanten > multipliziert (Fehler * konst). Der Fehler von pow ist aber größer:
1 | d(x^y) = x^y·(dx·y/x + dy·ln x) |
während der Fehler von Multiplikation:
1 | d(xy) = y·dx + x·dy |
Vielleicht solltest du dir die Konditionierung(en) nochmal anschauen? Selbt wenn pow für ganze Exponenten gesondert ausgewertet wird spart es dir nix. Der Vorteil von
1 | 11 + x·(7 + x·(5 - x·(4 + x·2))) |
gegenüber deinem Term ist dass diese Auswertung besser ist wenn die Reihenglieder klein werden, was man üblicherweise bei (Näherungen für) Potenzreihen hat. Generell gilt die Regel, dass "Strichrechnung vor Punktrechnung" besser konditioniert als umgekehrt, und genau das macht Horner.
Johann L. schrieb: > Der Fehler von pow ist aber größer: > d(x^y) = x^y·(dx·y/x + dy·ln x) > während der Fehler von Multiplikation: > d(xy) = y·dx + x·dy > Vielleicht solltest du dir die Konditionierung(en) nochmal anschauen? Mir geht es hier nicht um die Kondition ("wie werden externe Störungen verstärkt") sondern um Konsistenz ("welche zusätzliche Störung wird addiert"). Was ich ursprünglich sagen wollte ist ungefähr: Der Compiler darf die durch den Quelltext vorgegebene Konsistenz nicht ändern. Die Frage, wie der Compiler mit der gegebenen Kondition umgehen soll sorgt bei mir für UB ;-)
mh schrieb: > Johann L. schrieb: >> Der Fehler von pow ist aber größer: >> d(x^y) = x^y·(dx·y/x + dy·ln x) >> während der Fehler von Multiplikation: >> d(xy) = y·dx + x·dy >> Vielleicht solltest du dir die Konditionierung(en) nochmal anschauen? > > Mir geht es hier nicht um die Kondition ("wie werden externe Störungen > verstärkt") sondern um Konsistenz ("welche zusätzliche Störung wird > addiert"). Keine Ahnung welche Störungen du da noch addiertst. Auf die Konditionierung hat das keinen Einfluss; der ist es egal ob es um Rundungsfehler geht, Diskretisierungsfehler oder Messfehler oder was auch immer. Konditionierung ist eine Eigenschaft eines Ausdrucks / Algorithmus'. > Was ich ursprünglich sagen wollte ist ungefähr: Der Compiler darf die > durch den Quelltext vorgegebene Konsistenz nicht ändern. Der Compiler darf alles machen, was die Seiteneffekte nicht verändert. Und diese sind in der Sprachspezifikation geregelt. Gegebenenfalls kannst du diese Regeln aber lockern, bei GCC zum Beispiel -ffinite-math-only, -fassociative-math, -fno-signed-zeroes, -ffast-math, etc. > Die Frage, wie der Compiler mit der gegebenen Kondition umgehen soll > sorgt bei mir für UB ;-) Konditionierung ist ja auch keine Sache des Compilers, sondern des Algorithmus' der dem Compiler vorgeworfen wird. Wenn dein Code UB ist, kann der Compiler da nix für. Falls das Problem ist, dass Zwischenergebnisse den Werteberech verlassen, dann ist evtl. angezeigt, den Ausdruck nach Bernstein-Polynomen zu entwickeln und diese durch Kontrollpunkte darzustellen. Dann gilt nämlich: wenn alle Kontrollpunkte im Wertebereich liegen, dann auch alle (Zwischen)ergebnisse — sofern man die Polynome geschickt auswertet. I.d.R liegen die Kontrollpunkte nur wenig oder garnicht außerhalb des Bildbereichs. Bei genäherten Potenzreichen ist das i.d.R. nicht der Fall. Wenn man z.B. exp durch ihre McLaurin-Reihe nähert und damit exp(-10) berechnen will, explodieren die Zwischenergebnisse.
mh schrieb: > Für signed ints darf er es nicht, da evtl. auftretende Overflows > undefined behaviour sind. Ein compiler ist nicht verpflichtet bei UB etwas nicht zu dürfen.
Dumdi D. schrieb: > Ein compiler ist nicht verpflichtet bei UB etwas nicht zu dürfen. Es ist ihm aber gestattet.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.