Forum: Compiler & IDEs Compilertool: Gleichungen ausklammern


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Michael H. (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Μαtthias W. (matthias) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Hi

Hilft die dabei ein CAS wie etwa http://maxima.sourceforge.net/?

Matthias

von Markus F. (mfro)


Bewertung
0 lesenswert
nicht lesenswert
Octave kann das auch.

von leo (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Niklas G. (erlkoenig) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
Für allgemeine Ausdrücke kann Mathematica das auch. Leider nicht ganz 
billig. Wolfram Alpha reicht vielleicht auch

von Μαtthias W. (matthias) Benutzerseite


Bewertung
2 lesenswert
nicht lesenswert
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

von leo (Gast)


Bewertung
2 lesenswert
nicht lesenswert
Μα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

von mh (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Μα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.

von Michael H. (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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...

von Michael F. (michaelfu)


Bewertung
0 lesenswert
nicht lesenswert
Μα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)

von mh (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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,
auto square(unsigned int x) {
    return 11 + 7*x + 5*pow(x,2) - 4*pow(x,3) + 2*pow(x,4);
}
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
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,
>
> auto square(unsigned int x) {
>     return 11 + 7*x + 5*pow(x,2) - 4*pow(x,3) + 2*pow(x,4);
> }
> wird der numerische Fehler von pow nur mit einer Konstanten
> multipliziert (Fehler * konst).

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?

Selbt wenn pow für ganze Exponenten gesondert ausgewertet wird spart es 
dir nix.

Der Vorteil von
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.

von mh (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

von Johann L. (gjlayde) Benutzerseite


Bewertung
1 lesenswert
nicht lesenswert
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.

von Dumdi D. (dumdidum)


Bewertung
0 lesenswert
nicht lesenswert
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.

von S. R. (svenska)


Bewertung
0 lesenswert
nicht lesenswert
Dumdi D. schrieb:
> Ein compiler ist nicht verpflichtet bei UB etwas nicht zu dürfen.

Es ist ihm aber gestattet.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.