Mahte Ausdrücke vereinfachen

Ben04

Dies ist dein Program das Mathe Ausdrücke wie

(t*((z*b)^2*a/b*z+b*a*z))*c/t*z

zu

c*a*b*2

vereinfachen kann.

Es ist auch in der Lage Ausdrücke zu zeichnen, das heißt mit Bruchstrich und Exponenten. Desweiteren kann es auch ohne weiteres mit sehr großen Zahlen umgehen.

Dies ist die zweite Version die ich veröffentliche und dient größten Teils nur der Fehlersuche. Andere Leute finden oftmals Fehler die einem selbst nicht auffallen. Deshalb solltet ihr einen Fehler finden, sei es ein Absturtz, ein Zeichenfehler oder ein Rechenfehler, bitte postet hier mit dem eingegebenem Ausdruck und dem was das Program falsch gemacht hat.

Es handelt sich um das erste Program in dieser Liste:
http://www.dhost.info/voodoocpp/index.php?page=progs/progs
Zur Zeit ist nur ein Windowsbinary erhältlich. Der Code ist allerdings äußerst portabel gehalten.

Wenn jemand eine Idee hat wo man dieses Program verwenden kann dann wäre es nett sie zu äußeren. Es war zwar sehr interessant das Program zu schreiben, besonders sinnvoll is es so allerdings nicht.

Jester

Gib mal (a+b)*(a-b) ein.

Ben04

Ok das Problem wurde beseitigt. Neue Version hochgeladen.

Jester

Dein Ergebnis für x/x ist nicht richtig. Für 0 ist es undefiniert und nicht 1. Ist aber eher ne Kleinigkeit. Beim Eingeben von a/(a+b) ist er mir abgestürzt.

Ben04

Das Problem mit x/x ist mir bekannt. Im Moment wird das noch stillschweigend hingenommen. Ich hatte aber vor das in Zukunt auch noch zusätzlich ein Gütligkeits-Interval auszugeben. Im dem Fall wäre das dann 1 | x!=0 oder so etwas in der Art.

Das Problem mit a/(a+b) hab ich behoben. Neue Version hochgeladen.

Ich steht jetzt vor einem neuen Problem: a^(-1)*(a+b)(-1)
Wenn das Program das Distibutivegesetz anwendet dann sucht es nach Sachen wie a*(c+b) aber nicht nach a^b*(c+d)b. Muss ich wohl noch verbessern. Wird aber niht ganz trivial da bei zum Beispiel 7*(a+b)^3 Wurzeln her müssen damit daraus (7^1/3*a + 7^1/3*b)3.

Egal im Moment hab ich eh keine Zeit um mir darüber den Kopf zu zerbrechen.

Christoph

Ben04 schrieb:

Muss ich wohl noch verbessern. Wird aber niht ganz trivial da bei zum Beispiel 7*(a+b)^3 Wurzeln her müssen damit daraus (7^1/3*a + 7^1/3*b)3.

An dem Punkt würde ich mir nochmal genau überlegen, welche Darstellung du als "einfacher" definierst. Ich würde jedenfalls spontan "7*(a+b)^3" als einfacher bezeichnen, nicht die Formel mit 7^(1/3). Kann aber auch vom konkreten Anwendungsfall abhängen.

Gregor

Ben04: Das Projekt hört sich sehr interessant an. Ich hatte vor ein paar Jahren auch schonmal ganz naiv ein bischen was in diese Richtung gemacht und habe dann schnell gesehen, wie umfangreich das wird. Wie gehst Du denn an die Sache heran? Wie sieht dein Algorithmus in etwa aus?

Jester

a/(a+b) + b/(a+b) wird nicht vereinfacht.

Jester

(a^2-b2)/(a+b) wird auch nicht vereinfacht. Zudem ist hier die Darstellung irgendwie komisch. Das Minus verschmilzt mit den Bruchstrichen.

Ben04

Im Grunde genommen war das Ziel den Ausdruck zu expandieren und aus diesem Grund wird auch nicht aus a/c+b/c = (a+b)/c da es sich hierbei eigentlich um eine Faktorisirung handelt. Einfach ist wahrscheinlich als Wort schlecht gewählt allrdings bin ich mir auch alles anderes als sicher, dass man "expandieren" im Deutschen sagt. (Mathe ist bei mir auf Französich.) Jedenfals geht es drum alles in eine Summe zu verwandeln wenn möglich.

Dies ist auch nicht immer die "einfachste" Darstellung. (a+b)^100 ist wesentlich einfacher als a^100 + a^99*b*100 + a^98*b2*4950 + a^97*b3*161700 + ...

Fals der Weg dahin allerdings über eine Faktorisirung oder über die Benutzung der Formel a^b * c^b -> (a*c)^b (in die andere Richtung geht es) geht dann schafft es mein Program nicht. Bei ersterem weiß ich wie ich das Problem wahrscheinlich beheben kann. Beim letzteren hab ich bis jetzt nur ein kleine Idee. Wird aber sehr aufwendig da das Program die Faktorisirung vorher lernen muss.

Das Problem mit dem Minus und dem Bruchstrich ist leicht behoben.

@Gregor Es ist bei weitem nicht das einzige was ich bisher in diese Richtung gemacht hatte. Ich hatte schon ein paar Mal Interpreter vorher geschrieben die auch highlevel Optimirungen im Parsebaum vorgenommen haben (hätten sollten). Viel weiter als zum Inlinen um den Lookup des Funktionsnamen zu ersparen ist es aber nicht gekommen. Allerdings, auch wenn es nicht direkt ersichtlich, ist die Herangehensweise die Gleiche als bei diesem Projekt.

Man erstellt einen Parsebaum in dem man dann herumturnt und ihn verändert. Dabei gibt es eine Basisklasse von der alle Knoten abgeleitet sind. Also Zahlen, Summen und co. Die eingentlichen Algorithmen sind dann ganz einfache globale Funktionen die ihr Argument dann downcasten um darauf zu arbeiten. Es geht allerdings keine Funktion in die Tiefe des Baums sondern arbeitet nur auf einer festgelegten Tiefe. Meistens nur das erste Level. Zusätlich gibt es dann noch eine Zentrale Funktion die einen Funktionspointer übernimmt diese Funktionen dann für alle Knoten des Baums aufruft und zwar von Kind- zum Elternknoten hin.

Dies erlaubt es in der Klassenhierarchie herum zu werkeln ohne die Funktionen verändern zu müssen. Wenn eine neue Klasse mit Kindern hinzukommt dann muss nur die eine Funktion verändert werden. Alle anderen arbeiten weiter wie bisher.

Es ist auch eine gute Idee den Baum so klein wie möglich zu halten. Es gibt zum Beispiel keine Differencen oder Negationen. Mit Summen, Produkten und negativen Zahlen kann man das gleiche darstellen. Dies erschwert zwar das Einlesen und vor allem die Ausgaben allerdings müssen die eingentlichen Funktionen viel weniger Fälle unterscheiden. Hat allerdings auch den Nachteil, dass Formatirungsdetails verloren gehen. Fals einmal sin, cos und tan rein kommen sollten dann kommt nur pi, sin(x), sin(pi/2 - x) und sin(x)/sin(pi/2 - x) rein. Pi kommt rein da es nicht als Rationale Zahl dargestellt werden kann und der Zahlen Knoten mit Brüchen arbeitet.

Die eigentlichen Algrithmen sehen dann so aus:

Funktion expand(expr)
  if expr is Summe
    zähle alle möglichen Terme zusammen;
  else if expr is Produkt
    multiplizire alle möglichen Factoren zusammen;
    verteile sämtliche Factoren auf alle Terme des ersten Factor der eine Summe ist außer ihn selbst sofern es einen gibt;
  else if ...
  else
    tu nichts;
endfunktion

Ja ich weiß, downcasten is verpönt aber eine wirkliche Alternative hat mir für diesen Fall noch niemand zeigen können.

Mario Sandler

Ich kann dein Programm leider nicht testen (da nur eine windowsversion, die unter wine nicht stabil läuft), aber ich wollte sehen ob er eine wie ich finde interessante Aufgabe vereinfachen:

(a^x-a(x+2))/(a^(x+1)-ax)

bei mir ergibt das -a-1

kann mal einer testen?

auch diese Aufgabe ist sehr interessant und testwürdig:

(4^(n+1)+12*4n)/(4^(n+2)-4(n+1))

hierbei kriege ich 4/3 heraus.

PS: Gibts nen Latex-thread der erklärt wie man des benutzt?

Jester

Ben04 schrieb:

Ja ich weiß, downcasten is verpönt aber eine wirkliche Alternative hat mir für diesen Fall noch niemand zeigen können.

Wie wär's mit nem Visitor?

Gregor

Ben04 schrieb:

@Gregor Es ist bei weitem nicht das einzige was ich bisher in diese Richtung gemacht hatte. Ich hatte schon ein paar Mal Interpreter vorher geschrieben die auch highlevel Optimirungen im Parsebaum vorgenommen haben (hätten sollten). Viel weiter als zum Inlinen um den Lookup des Funktionsnamen zu ersparen ist es aber nicht gekommen. Allerdings, auch wenn es nicht direkt ersichtlich, ist die Herangehensweise die Gleiche als bei diesem Projekt.

Man erstellt einen Parsebaum in dem man dann herumturnt und ihn verändert. Dabei gibt es eine Basisklasse von der alle Knoten abgeleitet sind. Also Zahlen, Summen und co. Die eingentlichen Algorithmen sind dann ganz einfache globale Funktionen die ihr Argument dann downcasten um darauf zu arbeiten. Es geht allerdings keine Funktion in die Tiefe des Baums sondern arbeitet nur auf einer festgelegten Tiefe. Meistens nur das erste Level. Zusätlich gibt es dann noch eine Zentrale Funktion die einen Funktionspointer übernimmt diese Funktionen dann für alle Knoten des Baums aufruft und zwar von Kind- zum Elternknoten hin.

Dies erlaubt es in der Klassenhierarchie herum zu werkeln ohne die Funktionen verändern zu müssen. Wenn eine neue Klasse mit Kindern hinzukommt dann muss nur die eine Funktion verändert werden. Alle anderen arbeiten weiter wie bisher.

Es ist auch eine gute Idee den Baum so klein wie möglich zu halten. Es gibt zum Beispiel keine Differencen oder Negationen. Mit Summen, Produkten und negativen Zahlen kann man das gleiche darstellen. Dies erschwert zwar das Einlesen und vor allem die Ausgaben allerdings müssen die eingentlichen Funktionen viel weniger Fälle unterscheiden. Hat allerdings auch den Nachteil, dass Formatirungsdetails verloren gehen. Fals einmal sin, cos und tan rein kommen sollten dann kommt nur pi, sin(x), sin(pi/2 - x) und sin(x)/sin(pi/2 - x) rein. Pi kommt rein da es nicht als Rationale Zahl dargestellt werden kann und der Zahlen Knoten mit Brüchen arbeitet.

Die eigentlichen Algrithmen sehen dann so aus:
Funktion expand(expr)
  if expr is Summe
    zähle alle möglichen Terme zusammen;
  else if expr is Produkt
    multiplizire alle möglichen Factoren zusammen;
    verteile sämtliche Factoren auf alle Terme des ersten Factor der eine Summe ist außer ihn selbst sofern es einen gibt;
  else if ...
  else
    tu nichts;
endfunktion
Ja ich weiß, downcasten is verpönt aber eine wirkliche Alternative hat mir für diesen Fall noch niemand zeigen können.

Sah bei mir damals wohl so ähnlich aus. Bin mal gespannt, wie weit Du damit kommst. Momentan würde ich eher einen anderen Ansatz nehmen:

Ich würde erstmal die "Komplexität" eines Terms so ähnlich definieren, wie man in der Logik den Rang einer Formel oder ähnliches definiert. Dann hätte ich ein Maß, nach dem ich entscheiden könnte, welche Formel einfacher ist als eine andere.

Außerdem würde ich wohl eine Art Datenbank mit Umformungsregeln erstellen und die Formeln mittels Suche umformen lassen. Bis zu einer gewissen Suchtiefe würde ich halt alle Umformungen ausprobieren und mir dann die einfachste davon nehmen. ...vielleicht auch eine etwas gezieltere Suche, wenn mir da was einfallen würde.

...naja: Nur so als eingeworfene Idee. Der Nachteil dieser Idee ist sicherlich, dass die Suche unter Umständen sehr zeitaufwändig ist. Ich glaube, etwas ähnliches hatten auch schonmal einige in diesem Forum ausprobiert. Keine Ahnung, was daraus geworden ist.

Ben04

@Storm.Xapek.de
Im Matheforum is so ein Topic sticky gemacht.

Das Problem ist, dass deine beide Beispiele über eine Faktorisirung gehen.

(a^x-a(x+2))/(a^(x+1)-ax)
=a^x(1-a2)/a^x(a-1) <<< Faktorisirung
=(1-a^2)/(a-1)
=(1-a)(1+a)/(a-1) <<< Nochmal
=-1-a

Ich glaub nicht, dass das noch was vor den nächsten Ferien was wird da die Faktorisirung doch bedeutent schwieriger ist als das was bisher da ist.

@Jester
Was erspar ich mir dabei?

Ob ich jetzt den Spagat mache um den Visitor zu implementiren und dann

struct Visitor{
  void bar(Base*){
  }
};

struct Foo:public Visitor{
  void bar(A*){
    //...
  }
  void bar(B*){
    //...
  }
  void bar(C*){
    //...
  }
  // D benutzt default

};

oder

void bar(Base*base){
  if(A*a = dynamic_cast<A*>(base)){ 
    //...
  }else if(B*b = dynamic_cast<B*>(base)){
    //...
  }else if(C*c = dynamic_cast<C*>(base)){
    //...
  }else{
    // D benutzt default
  }
}

schreibe ist ja nur ein syntaktischer Unterschied. Ich muss genau soviele Fälle unterscheiden und hab genau soviele Abhängigkeiten und ähnlich viel Freiheiten.

Die Rekusion hab ich ja auch in eine eigene Funktion ausgelagert. Vielleicht kann man es auch so sehen, dass ich die Funktionen als Visitor benutze.

Ausdrücke wie a*b + a*c und sogar a^n + a^(n+1) sollten leicht zu Faktorisiren sein. Ich setzt alles was alle Terme gemeinsam haben heraus. Allerdings bereiten mir Sachen wie a^2 - b^2 Kopfzerbrechen. Die haben nix gemeinsam und sind doch faktorisirbar.

@Jester Diese Idee hatte ich auch schon allerdings ist die Implementirung äußerst komplex und die Laufzeit ist katastrophal. Die erste Formel gibt 2 mögliche Schritte die zweite wieder 2. Das macht schon 4! Möglichkeiten. So die Mathematik ist ja nun nicht so fromellos und wenigstens sämtliche Anxiome müssen da rein. Dann kommt da noch die Größe des Ausdrucks dazu. Das sind schnell Bäume mit vielen Knoten also schon wieder viele mögliche Kobinationen.

Dann hast du noch immer nicht das a^2-b2 Problem gelöst denn die Formel ist zwar leicht herzuleiten aber nur in die eine Richtung und dann ist die andere Richtung als Nebenprodukt ja mit bewiesen. Ich wüsste nicht wie ich a^2-b2 -> (a+b)(a-b) beweisen soll ohne darauf zurück zu greifen, dass ich das Resultat ja an sich kenne.

Jester

Ben04 schrieb:

@Jester
Was erspar ich mir dabei?

Du sparst Dir den häßlichen cast. Außerdem könntest Du dann unterschiedliche Visitors bauen, einen der eher zusammenfast, einen der ausklammert etc.
Die kannst Du dann einfach auf Bäume oder Teilbäume loslassen. Außerdem finde ich es schöner, einfach eine neue Überladung hinzuzufügen, als immer ein häßliches if-Statement zu überarbeiten.

Ben04

Verschiedene Funktione hab ich ja bereits

template<class F>
void apply_to_tree(const Expression&expr, const F&f){
  if(expr is sum)
    for all terms 
      apply_to_tree(*term, f);
  else if(expr is prod)
    for all factors 
       apply_to_tree(*factor, f);
  else if(...)
    ...
  f(expr);
}

So nun kann ich ohne weiteres jede Funktion auf den Baum loslassen. Daten sammeln geht auch wobei ich da doch eine leicht andere Variante benutze die mit Rückgabewerten arbeitet. Neue Elemente mit Kindern hinzufügen geht auch leicht.

Den Cast zu verstecken bringt auch nicht viel, da bevorzuge ich doch lieber die direkte Art sich auszudrücken und zu sagen was Sache ist.

Jester

Was ist damit:
Operator * op = new Ausklammerer();
tree->apply(op);
an anderer Stelle: op = new IrgendneAndereClevereStrategie();

Zudem der Vorteil, daß Du in der Klasse die Überladung nur dazuschreiben mußt und sie wird korrekt genutzt. Ohne ein großes if-Statement zu basteln. Bei virtuellen Methoden benutzt Du das doch auch und sagst nicht, "ich will sehen was da passiert, das ist besser" und baust Dir dann ne eigene vTable.

Ben04

Jester schrieb:

Was ist damit:
Operator * op = new Ausklammerer();
tree->apply(op);
an anderer Stelle: op = new IrgendneAndereClevereStrategie();

Sorry, aber da verstehe ich nicht was du meinst.

Jester schrieb:

Zudem der Vorteil, daß Du in der Klasse die Überladung nur dazuschreiben mußt und sie wird korrekt genutzt.

Bei einem if muss ich auch nur ein if else hinzfügen.

Jester schrieb:

Bei virtuellen Methoden benutzt Du das doch auch und sagst nicht, "ich will sehen was da passiert, das ist besser" und baust Dir dann ne eigene vTable.

Dies hat aber haupsächlich den Grund, dass der Compiler mir auch einen Teil der Arbeit abnimmt. VTable mit den Klassen syncron zu halten ist nicht gerade eine interessante Beschäftigung. Desweiteren muss ich viel Code schreiben um einen self-made-VTable zu nutzen wogegen dies mit virtual sich auf die Benutzung von ein paar Keywords beschränkt. Beide Vorteile sind für das Visitor pattern nicht gegeben.

Es sind mir auch noch zwei Nachteile des Visitor patterns gegenüber meiner jetztigen Implementirung aufgefallen.

Beim Visitor müssen alle Visitors von einer Basisklasse abgeleitet werden. Wogegen mit meinem apply_to_tree dies nicht gefordert ist. Dies erlaubt zum Beispiel den einfachen Einsatz von boost::bind und ähnlichem.

Dann hab ich noch folgende sehr nützliche Funktion:

void explode_pow(const Expression&expr, const Expression*&base,const Expression*&exp){
  if(const Power*pow = expr_cast<const Power*>(expr)){
    base = &(pow->base);
    exp = &(pow->exp);
  }else{
    base = &expr;
    exp = &get_one_expr();
  }
}

Diese kann man als Alternative zum if-Konstrukt einsetzen und erlaubt es in manchen Situationen ganz auf eine Fallunterscheidung zu verzichten. Mit einem Visitor hab ich mich aber auf eine Fallunterscheidung festgebunden.

Desweiteren ist bei meiner Lösung die Klassenhierarchie völlig unabhängig von den Algorithmen die darauf arbeiten. In diesem Fall ist dies zwar egal, könnte man aber als Nachteil des Visitorpatterns auslegen da er nicht einfach auf bereits bestehende Hierarchien angewant werden kann.

Ich hatte am Anfang auch einmal das Visitorpattern zu test umgesetzt. Hab es aber wieder schnell verworfen da mir keinerlei Vorteile außer ein wenig Syntaxzucker im Benutzercode auf fiehlen.

Swordfish

Ben04 schrieb:

Jester schrieb:

Bei virtuellen Methoden benutzt Du das doch auch und sagst nicht, "ich will sehen was da passiert, das ist besser" und baust Dir dann ne eigene vTable.

Dies hat aber haupsächlich den Grund, dass der Compiler mir auch einen Teil der Arbeit abnimmt. VTable mit den Klassen syncron zu halten ist nicht gerade eine interessante Beschäftigung. Desweiteren muss ich viel Code schreiben um einen self-made-VTable zu nutzen wogegen dies mit virtual sich auf die Benutzung von ein paar Keywords beschränkt. Beide Vorteile sind für das Visitor pattern nicht gegeben. [

Mensch...

Jester

Ben04 schrieb:

Desweiteren ist bei meiner Lösung die Klassenhierarchie völlig unabhängig von den Algorithmen die darauf arbeiten.

Ist sie beim Visitor doch auch. Du machst ja nur die Schnittstelle bekannt. Die ganzen konkreten Implementierungen sind der Klassenhierarchie nicht bekannt.