3. C/C++ symbolische Mathematik beibringen...

C/C++ symbolische Mathematik beibringen...

  • V

    habe ein probem.
    ich schlug den bronstein auf und fand da ne tabelle unbestimmter inegrale.
    die erste formel sieht wohl so aus:
    int( (A*X+B)^N , X , (1/(A*(N+1))(AX+B)^(N+1) ):-
    const(A,X),
    const(B,X),
    const(N,X),
    N \= -1;
    also kein gezappele mit
    int( X^N , ...
    , sondern gleich ne allgemeinere form.
    von diesen allgemeinen formen finden sich 515 stück in der tabelle.
    ist ja auch eigentlich sehr toll. nur so kriegt man einigermaßen
    viele integralformeln unter, ohne endlos viel code zu schreiben.
    wenn nun unser integralsucher aber ein x^17 vor sich sieht, kriegt
    der das doch überhaupt nicht auf ne form wie (1x+0)^17, die in prolog
    matchen würde.
    erlaube ich aber dem automaten, den term immer weiter zu komplizieren, bis
    er x^17 auch mal zu (1    x+0)^17 umgewandelt hat, dann gibt es keine grenze
    den komplizierens. warum nicht (1*x+0)^(1*17+0*1)?
    bei versuchen kam aus a+b+c fein so schrott wie ((a*1+b*1)*1+c*1)*1 raus,
    aber nach wenigen tausend solchen termin ist der local stack voll und das
    programm bricht ab.

    0
  • J

    Kannst Du ihn vielleicht doch mit dem normalen x^n versorgen und das da über Substitution lösen?

    0
  • V

    Jester schrieb:

    Kannst Du ihn vielleicht doch mit dem normalen x^n versorgen und das da über Substitution lösen?

    hab was besseres.
    ein prädikat match, das die verkomplizierungen macht.
    zum beispiel
    match(1X+0,X).
    und wenn ich dann mal nen paramterer brauche, der wie A    X+B aussieht, kann ich das prädikat matchen lassen, statt es in prolog direkt hinzuschreiben.

    und ne andere bedeutung kriegt match auch noch:
    match löst auch das problem mit
    a*b+b*a, denn die alte formel
    simplify(X+X,2X).
    wird ersetzt durch
    simplify(X+Y,2    X):-
    match(X,Y).

    match muss rausfinden können, ob zwei terme gleich sind. sollte eigentlich gehen, indem produkte ausgeklammert werden, bis nur noch ne summe von produkten dasteht, und dann kann man ja die summanden vergleichen (hoffentlich).
    also ich brauche jetzt was, was feststellt, ob zwei terme gleich sind. und komme wiedermal nicht weiter. das ausklammern kriege ich schon nicht hin.

    0
  • T

    Einen Match bekommst du mit "=". Also: T=sin(_)
    Wenn in T irgendwo ein sin(bla bla bla) steht, TRUE.
    Es kann auch vor und hinter dem Sinus nach was kommen -> ist egal.

    Wenn zwei Terme gleich sein sollen, muss man wohl beide miteinander
    matchen:

    match(A,B,deine Rückgabe) :- A=B, B=A.

    EDIT:
    Man kann natürlich T=sin(D) sagen. Dann wird das Argument von Sinus
    dem D zugewiesen etc.

    0
  • T

    Jester schrieb:

    Da wär ich aber vorsichtig bei der Divisionsregel:

    X/X==>1 definert auch 0/0 zu 1. Ich würde lieber noch X!=0 fordern.
    Aufpassen mußte auch pei Potenzen:

    sqrt(x^2) = abs(x), nicht x.

    Die Division durch null würde ich noch extra definieren!
    Aber der Betrag von x, statt x ... das hatte ich noch
    nicht beachtet, danke.

    0
  • T

    volkard schrieb:

    ths schrieb:

    Also ich werde das Projekt weiter
    fortsetzen 👍 Just for fun 🙂

    und just for fun könntest du noch ein paar testfälle sammeln. bin zwar noch lange nicht so weit, und teste noch gar nix, aber wenn du schon welche hast, wenn ich sie bald brauche, ist das nett.

    Ja klar. Werde am Wochenende mal die Testfälle sammeln. Ich teste die Testfälle
    mit einem TI-89 und dem PC. Oder wenn sie trival sind, eben so... 😉

    0
  • T

    volkard schrieb:

    ich schlug den bronstein auf und fand da ne tabelle unbestimmter inegrale.
    von diesen allgemeinen formen finden sich 515 stück in der tabelle.

    ist ja auch eigentlich sehr toll. nur so kriegt man einigermaßen
    viele integralformeln unter, ohne endlos viel code zu schreiben.

    Nun... wir müssen eine Entscheidung treffen.

    Hintergrund:
    Wenn du diese allgemeinen 500 Möglichkeiten in einen TI-89 eingibst, dann
    kann der bei weitem auch nicht alle vereinfachen! Warum soll unser CAS
    das dann können?

    So wie ich das gelesen habe, ist das Derive CAS sehr sehr klein (ein paar
    MB in der PC-Fassung). ( http://www.derive-europe.com/specs.asp?screenshots )
    Übrigens: Derive läuft auch auf dem TI-89 und dem TI-92 (Plus)!!! So klein
    war es mal.

    Dagegen ist Mathematica und Maple wohl sehr schwer-gewichtig (vom Speicher
    her). Nun kann ich mir gut vorstellen, dass ein Maple noch einiges mehr
    vereinfachen kann, als ein Derive (das so klein ist, dass es auf einem
    Taschenrechner läuft).

    Mit anderen Worten:
    Wollen wir einen symbolischen Rechner, der zuverlässig die häufigsten
    Sachen vereinfachen kann .... oder wollen wir ein Maple schreiben, dass
    ALLES lösen kann?

    In dem Fall, dass man einen Maple-Ersatz schreiben will, kann man auch
    die 500 Zeilen tippen -- das ist legitim.

    Und im Derive-Fall gibt man sich mit den etwas längeren Termen zufrieden 😉

    wenn nun unser integralsucher aber ein x^17 vor sich sieht, kriegt
    der das doch überhaupt nicht auf ne form wie (1*x+0)^17, die in prolog
    matchen würde.

    Was meinst du? Meinst du X^17, statt x^17? Also einen beliebigen Term
    hoch 17...

    0
  • V

    ths schrieb:

    Einen Match bekommst du mit "=". Also: T=sin(_)
    Wenn in T irgendwo ein sin(bla bla bla) steht, TRUE.
    Es kann auch vor und hinter dem Sinus nach was kommen -> ist egal.

    ich kann doch jetzt prolog. das war mir klar.

    Wenn zwei Terme gleich sein sollen, muss man wohl beide miteinander
    matchen:
    match(A,B,deine Rückgabe) :- A=B, B=A.
    EDIT:
    Man kann natürlich T=sin(D) sagen. Dann wird das Argument von Sinus
    dem D zugewiesen etc.

    [/quote]
    das reicht mir aber nicht. matchen mit = findet keinen match bei
    match(a+b,b+a).
    deswegen will ich mir doch erlauben, ne match-klausel zu benutzen.
    ungefähr so:
    match(A,A).
    match(A*B,B*A).
    match(A+B,B+A).
    match(A,A1).
    und noch ein paar...
    und unten
    simplify(A+B,2    A):-
    match(A,B).
    so schafft er es, aus
    bla*blubb+blubb*bla ein 2*blubb zu machen.
    vielleicht sollte ich das match in dieser verwendung eher equals nennen.

    0
  • V

    volkard schrieb:

    match muss rausfinden können, ob zwei terme gleich sind. sollte eigentlich gehen, indem produkte ausgeklammert werden, bis nur noch ne summe von produkten dasteht, und dann kann man ja die summanden vergleichen (hoffentlich).

    geht nicht immer.
    was soll er aus (1-sin(a)2)*x2 und cos(a)2*x2 machen? sie sind gleich, aber das wird er vermutlich nie sehen.
    den ansatz mit dem ausklammern ging http://www.furchur.de/files/labore/logprog/symbdiff.pdf bereits sehr wert. die ergebnisse sind auch beeindruckend.

    0
  • V

    ths schrieb:

    Mit anderen Worten:
    Wollen wir einen symbolischen Rechner, der zuverlässig die häufigsten
    Sachen vereinfachen kann .... oder wollen wir ein Maple schreiben, dass
    ALLES lösen kann?

    ALLES versuchen und bald aufgeben.

    Was meinst du? Meinst du X^17, statt x^17? Also einen beliebigen Term
    hoch 17...

    ich meinte es in
    int( (A*X+B)^N , X , (1/(A*(N+1))(AX+B)^(N+1) ):- ...
    und dann im aufruf
    int(x^17,x,R).
    x^17 wird nicht auf (AX+B)^N matchen können, weshalb die integrierklausel übersehen wird.
    macht man aber
    int( M , X , (1/(A    (N+1))(AX+B)^(N+1) ):-
    match(M,AX+B),...
    dann kann man an anderer stelle beschreiben, was matchen soll, und zwar nicht nur das prolog-matchen:
    match(A,A).
    sondern auch ein erweitertes:
    match(1    A,A).
    match(A+0,A).
    match(1*A+0,A).
    damit kommt man schon verdammt weit, fürche ich.
    um mehr zu kriegen, muß match eigentlich matchen, wenn der eine teil *irgendwie* in den anderen teil überführbar ist. angenommen, simplify würde unabhängig von match funktiponieren, und schon laufen:
    match(A,B):-
    simplify(A-B,0).%wenn die differenz gleich 0 ist, sind die terme gleichwertig.

    0
  • T

    Also deine Idee mit den Match-Prädikaten ist interessant. Das werde ich mir
    mal genauer ansehen -- nach meinem TV-Nachmittag 😉

    Und die Lösung in dem PDF-Dokumnt ist ja beeindruckend. Schön sauber und
    recht kurz. Ich bin bei ~ 230 Zeilen im Moment... und es sieht mehr wie
    Kraut und Rüben aus :p Aber solange man noch durchsteigt...
    230 Zeilen inklusive Kommentare natürlich 😉

    0
  • V

    ths schrieb:

    Ich bin bei ~ 230 Zeilen im Moment... und es sieht mehr wie
    Kraut und Rüben aus

    ich bin erst bei 26 zeilen. 🕶

    0
  • V

    mal zum ALLES-ansatz:
    mit

    termTrans(Term,Result):-
  Term=..[Functor|Args],
  maplist(termTrans,Args,TArgs),
  Term2=..[Functor|TArgs],
  trans(Term2,Result).

    kann man von eime term alle subterme durch ein prädikat trans/2 schicken.

    trans/2 kann weitgehend aus einem mathebuch abgeschrieben werden.

    % zusammenfassen von atomen
trans(A+B,C):-
  number(A),
  number(B),
  C is A+B.

% steht in selten im mathebuch, aber ein term ist er selbst
trans(A,A).

% Kommutativgesetz der Addition
trans(A+B,B+A).

% Assoziativgesetz der Addition
trans(A+(B+C),(A+B)+C).
trans((A+B)+C,A+(B+C)).

% Neutrales Element der Addition
trans(A,A+0).
trans(A+0,A).

% Kommutativgesetz der Multiplikation
trans(A*B,B*A).

% Assoziativgesetz der Multiplikation
trans(A*(B*C),(A*B)*C).
trans((A*B)*C,A*(B*C)).

% Neutrales Element der Multiplikation
trans(A,A*1).
trans(A*1,A).

% Distributivgesetz
trans(A*(B+C),A*C+B*C).
trans(A*C+B*C,A*(B+C)).

    der aufruf für a+a

    process(Term):-
  termTrans(Term,V),
  writeln(V),
  fail.
process(_).

:-
%  Term=a*b*c + a*c*b + b*a*c + b*c*a + c*a*b + c*b*a,
  Term=a+a,
  process(Term).

    erzeugt auch lecker viele varianten.

    a+a
a+a
a+a+0
(a+a)*1
a+ (a+0)
a+0+a
a+a+0
a+ (a+0)+0
(a+ (a+0))*1
a+a*1
a*1+a
a+a*1+0
(a+a*1)*1
a+0+a
a+ (a+0)
a+ (0+a)
a+0+a+0
(a+0+a)*1
a+0+ (a+0)
a+0+ (a+0)
a+0+a+0
a+ (0+ (a+0))
a+0+ (a+0)+0
(a+0+ (a+0))*1
a+0+a*1
a*1+ (a+0)
a+ (0+a*1)
a+0+a*1+0
(a+0+a*1)*1
a*1+a
a+a*1
a*1+a+0
(a*1+a)*1
a*1+ (a+0)
a+0+a*1
a*1+a+0
a*1+ (a+0)+0
(a*1+ (a+0))*1
a*1+a*1
a*1+a*1
a*1+a*1+0
(a*1+a*1)*1
a* (a+1)

    schickt man die weider in den selben transformator, wird er aus a*1+a*1
    auch a*(1+1) machen und danach daraus a*2.

    beim wiederbeschicken sollte man vorher die ergebnisliste nach komplexität sortieren
    und zuerst die kleinsten reinschicken. große monster voller *1+0 halten dann nicht
    so lange auf.
    sortieren nach komplexität geht ja auch.

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% kostenfunktion für terme

% ein atom kostet nichts
cost(Term,0):-
  atomic(Term),
  !.

% jede funktion kostet 1
cost(Term,Cost):-
  Term=..[_|Args],
  maplist(cost,Args,Costs),
  sumlist(Costs,CostsSum),
  Cost is CostsSum+1.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% vergleich nach kosten

% bei gleichen kosten zieht der normale termvergleich
compareByCost(R,A,B):-
  cost(A,CA),
  cost(B,CB),
  compare(=,CA,CB),
  compare(R,A,B),
  !.

% bei ungleichen kosten ziehen die kosten
compareByCost(R,A,B):-
  cost(A,CA),
  cost(B,CB),
  compare(R,CA,CB).

    und wenn man dazu noch macht, daß terme, die bereits einmal als quelle der umformungen
    benutzt wurden, nicht mehr weiter beachtet werden (mit dem global dictionary), frisst
    er sich immer weiter in komplexere terme, bis er mal ne tolle vereinfacheung findet.

    und wenn man dann sobald ne tolle vereinfachung stattfand (kosten des gefundenen terms
    kleiner als kosten des ausgangsterms) ein cut setzt (alle lokalen stacks löscht), das
    dictionary leert und von vorne anfängt, müßte man auch die speicherexplosion einigermaßen
    im griff haben.

    ich kommentiere mal die regeln für die neutralen elemente aus.
    ausgabe:

    a+a
a+a

    jo, das ist gut.

    jetzt der lange term, der mir so kopfzerbrechen bereitet.

    Term=a*b*c + a*c*b + b*a*c + b*c*a + c*a*b + c*b*a,

    oh, das werden aber viele. vieele! vieeeele!!!!
    in jedem baumknoten bringt er eine unveränderte version und eine vertauscht.
    das sind mal locker 2 hoch knotenanzahl stück.

    ich leite die ausgabe in ne datei um, um dem wachsen derer zugucken zu können...
    100k...
    1M...
    3M...
    10M...
    bei 1G hört er auf, mehr platz hab ich auf der platte nicht.

    schade eigentlich.

    das zwingt dazu, nicht allein die körperaxiome als ausgang für umformungen zu nehmen,
    sondern andere sachen. zum beispiel sollte a*b*c nicht ((a,b),c) sein, sondern
    *(a,b,c). und vertauschungen sollten immer irrelevant sein.

    gegen die explosion gibts noch weitere tricks. man gibt dem transTerm ein MaxCost mit,
    und probiert zuerst nur transTerm(M,Term,Ergebnis) mit M=kosten von Term. nor wenn das
    zu keiner vereinfachung führt, erlaubt man im nächsten durchlauf eins mehr als MaxCost.
    also recursive deepening.

    0
  • T

    Das ist heftig... 😮

    Auf jeden Fall ein prima Ansatz 🙂 Ich bin da einen ganz anderen Weg
    gegangen, daher auch > 200 Zeilen 😉 Im Moment habe ich alles nur mit
    Prädikaten ganz simpel definiert. Ohne Listen etc., ohne so tiefe Rekursion...

    Daher hab ich das Problem nicht, dass der Stack überläuft, oder das solche
    Datenmengen produziert werden. Dafür bekommt man aber nicht immer den perfekt
    vereinfachten Term. Gerade bei solchen Sachen wie...
    b*c + a*c*b + b*a*c + b*c*a + c*a*b + c*b*a
    ... hat er natürlich Probleme.

    Da gäbe es einen anderen Ansatz:
    Wenn man das Prolog-Programm weiter schreiben will, sollte man am Ende ja
    eh eine grafische Oberfläche in C++ der Java dazu schreiben. Ich hab mir mal
    ein paar Java-Interfaces für Prolog angesehen: Bei einem ist es sogar so, dass
    man im Prolog-Programm Methoden aus Java benutzen kann!!!

    Nun ja... nichts leichter als das. Dann gib ich solche Terme, wie oben, zuerst
    an Java zurück, dort werden sie sortiert, und dann ist das eine Kleinigkeit
    für Prolog.

    Für C / C++ wird es sicher auch so'n Interface geben, wo man Funktionen oder
    Methoden aufrufen kann.

    Ich bastel aber an diesen Problemen im Moment nicht weiter, sondern hab es
    hingenommen, dass man es nicht ohne Probleme lösen kann (diese a+b... Terme).
    Hab statt dessen mit Division weiter gemacht. Ist garnicht so einfach, dass
    Prolog in jeder Lebenslage eine Division durch Null erkennt, und als Ergebnis
    dann 'undefined' präsentiert 😃 Habs aber...

    Naja... die n-te Wurzel hab ich auch schon drinne. Und da ich alle Wurzeln in
    Potenzen umwandel, komme ich jetzt mit der Division also an die komplexen
    Zahlen 🙄 Da werde ich wohl erstmal auch 'undefined' oder
    'not real' zurück geben.

    0
  • V

    ths schrieb:

    Nun ja... nichts leichter als das. Dann gib ich solche Terme, wie oben, zuerst an Java zurück, dort werden sie sortiert, und dann ist das eine Kleinigkeit für Prolog.

    nur für's zusammenfassen und sortieren würde ich nicht gleich ne andere sprache nehmen. das geht auch noch in prolog.

    ich schau gerade mal, ob sich das fein in c++ machen läßt, ohne zu viele vorteile von prolog afzugeben.

    0
  • C

    Hab mir gard aus Langeweile mal alles durchgelesen da ich auch mal sowas in der Art versucht hab.
    Ihr macht das bestimmt besser als ich 🙂

    P.S.:
    Bei den ganzen Varianten von a+a = a+0+a ...stimmts am Ende nicht mehr !
    a+a != a*(a+1)

    Greetz

    0
  • C

    ERROR

    0
  • J

    chr1s schrieb:

    Bei den ganzen Varianten von a+a = a+0+a ...stimmts am Ende nicht mehr !
    a+a != a*(a+1)

    Sorry, aber da fehlt mir jetzt echt der Zusammenhang. Was soll nicht stimmen?

    0
  • C

    ich bezog mich auf den längsten deiner posts auf der vorigen Seite.
    aber is nich so wichtig...

    0
  • V

    chr1s schrieb:

    Bei den ganzen Varianten von a+a = a+0+a ...stimmts am Ende nicht mehr !
    a+a != a*(a+1)

    jo.
    wenn ich recht gucke, liegt der fehler an
    trans(A*C+B*C,A*(B+C)).

    0
Anmelden zum Antworten