Mathe Ausdücke vereinfachen

Ben04

Dies ist ein Programm das Mathe ausdrücke expandieren und (oft) faktorisieren kann.

Falls jemand einen Fehler findet, das heißt Absturz oder glaubt, dass man an einem Ausdruck noch weiter vereinfachen kann, bitte postet. Andere Komentare sind natürlich auch willkommen.

Screenshot
Windows Binary

Gregor

Ich habe es zwar nicht ausprobiert (u.a. weil ich gar kein Windows nutze), aber ich finde so ein Programm interessant.

Wie hast Du das mit dem Vereinfachen gemacht? Wie entscheidest Du, was einfacher und was komplizierter ist? Ich hatte vor Jahren mal etwas ähnliches geschrieben und da ist das Vereinfachen sehr schnell in eine riesige if-Orgie ausgeartet. ...wobei die Ausdrücke da allerdings auch komplexer sein konnten, als das Beispiel, was Du da auf dem Screenshot zeigst.

Ben04

Nun "einfach" ist so eine Sache. Es gibt eindeutige Fälle (1+1 = 2) aber es gibt auch viele andere. Ich hab entweder faktorisieren oder expandieren als Ziel eingestellt und dann ist es meistens klar und wenn nicht dann mach ich das was ich als das beste halte. Die Frage ob a/b oder a*b^-1 geh ich aus dem Weg indem ich nur letztere unterstütze. Bei der Ein- und Ausgabe wird es aber als erstes angezeigt.

Wenn man das ganze inlinen würde kämme es sicher auch auf eine riesige if-Orgie raus. Man muss halt sehr viele Abstraktionsniveaus einziehen um den Code wartbar zu halten.

wobei die Ausdrücke da allerdings auch komplexer sein konnten, als das Beispiel, was Du da auf dem Screenshot zeigst.

Bei mir sind drin:

Summen (und Differenzen)
Produkte (und Divisionen)
Exponenten (und Wurzeln aber keine Logarithmen)

Als Operationen sind implementiert:

Expansion
(Reale) Faktorisation für Summen bis zu 4 Termen. Allerdings kriegt die nicht alles raus, Polynome des 3ten Grad sind in der Regel nicht lösbar.

Einfach sollte es auch noch sein eine Ableitungsoperation zu bauen.

War bei [edit]dir[/edit] sonst noch etwas drin.

Gregor

Ben04 schrieb:

War bei sonst noch etwas drin.

Fehlt da ein "Dir"?

Ich hatte da vor allem trigonometrische Funktionen und so Zeugs mit drin, in deren Zusammenhang sich natürlich jede Menge Vereinfachungen ergeben.

Wenn ich soetwas nochmal bauen würde, würde ich mir überlegen, das als Regelbasiertes System zu konstruieren. ...irgendwo alle Regeln abspeichern und dann mit Suche arbeiten. Es ist auf Dauer glaube ich nicht handhabbar alle Regeln in irgendeiner Form im Quellcode zu haben.

Mein System konnte damals ableiten. Das ist interessanterweise deutlich unproblematischer als das Vereinfachen von mathematischen Ausdrücken.

Ben04

Gregor schrieb:

Ben04 schrieb:

War bei sonst noch etwas drin.

Fehlt da ein "Dir"?

Ja, hab es hinzugefügt.

Gregor schrieb:

Ich hatte da vor allem trigonometrische Funktionen und so Zeugs mit drin, in deren Zusammenhang sich natürlich jede Menge Vereinfachungen ergeben.

Wenn ich soetwas nochmal bauen würde, würde ich mir überlegen, das als Regelbasiertes System zu konstruieren. ...irgendwo alle Regeln abspeichern und dann mit Suche arbeiten. Es ist auf Dauer glaube ich nicht handhabbar alle Regeln in irgendeiner Form im Quellcode zu haben.

Das hab ich mir auch schon überlegt. Allerdings müssen IMHO Grundkonstrukte hardgecodet sein aus Geschwindigkeitsgründen und um Implementierungsdetails zu verstecken. Zum Beispiel der Unterschied zwischen 2 (einer Zahl), 2 (einem Produkt mit einem Faktor) und 2 (einer Summe mit einem Term) oder a+b = b+a.

Formel wie a^2+(-b2) -> (a-b)*(a+b) könnte man wahrscheinlich aus einer Formel Datenbank entnehmen. Ist wahrscheinlich aber nicht sonderlich schnell.

Anderseits wieso sollte etwas hardgecodete viel schneller sein? Es handelt sich ja doch um den gleichen langsamen Algorithmus. Müsste man ausprobieren.

Gregor schrieb:

Mein System konnte damals ableiten. Das ist interessanterweise deutlich unproblematischer als das Vereinfachen von mathematischen Ausdrücken.

Ich weiß man braucht nur die äußere Ableitung der einzelnen Teile der Baumstruktur : Einfaches Formel-Anwenden (außer man hat da ein abs drin...) und für den Rest [f(g(x))]' = f'(g(x))*g'(x). Nun braucht man "nur" noch eine Funktion um den Ausdruck zu vereinfachen.

Hattest du komplexe Zahlen drin? Fals ja würd mich interessieren wie du i^(1/2) gehandhabt hast.

Gregor

Ben04 schrieb:

Hattest du komplexe Zahlen drin?

Ne.

ronny

hmm - für sowas ist prolog geeignet - damit kann man recht nett regeln schreiben, u.a. weil sie das grundkonzept der sprache sind

Ben04

Da würde mich ein konkretes Beispiel interessieren. Ich kenne Prolog ein wenig sehe aber nicht wie man das da einfacher als in C++ realisieren sollte.

maximAL

einfacher schonmal, weil man sich mit einem dialekt wie SWI prolog schon nicht mal mehr um das parsen der eingabe-funktion kümmern muss, weil der unifikations-algorithmus schon so mächtig ist, dass man im prinzip nur noch eingabe -> ausgabe hinschreiben muss.
ich kenn ja deinen code nicht, aber ich wär schon schwer überrascht, wenn der ebenso kurz und lesbar wie ein entsprechendes prolog program ist.
ich hab mal einen einfachen integrator für grundintegrale (inkl. summanden, quotienten, faktoren etc.) gebaut, das war kaum mehr als die formelsammlung abzutippen:

% integrator
% Hinweise:
% 1.) Entsprechend der Aufgabenstellung erfolgt keine Vereinfachung der integrierten Formeln
% 2.) Ebenso erfolgt keine Vereinfachung der zu integrierenden Formeln,
% da diese Funktionalität im wesentlichen 1.) entspricht. 
% Somit sind zu integrierenden Formeln vorher zumindest trivial zu vereinfachen
% 3.) Aus 2.) folgend gelten Kommutativ -u. Assoziativgesetze nur für paarweise Operanden
% 4.) Aus 2.) und 3.) folgend sollten Operanden paarweise geklammert werden
% 5.) Negative Faktoren sollten in der Forma -1 * n ausgedrückt werden
% 6.) Subtrahenten sollten in der form a+ -b angegeben werden
% 7.) Für Integrale der form f'/f muss beachtet werden, dass f in der Form stehen muss, % die inte(f, R) ermittelt
% 8.) Wurzeln werden in der Form root(n, Formel) angegeben, 
% zb. root(2, X) für Quadratwurzel
% 9.) x ist als Variable definiert und darf somit nicht als Konstante genutzt werden

% Hilfsprädikate für Konstanten (reelle Zahlen als auch "Text")
% auch zusammengesetze Gebilde (1 / 2, 3 * (2 + b) etc.) sind erlaubt
const(A):- atomic(A), not(A = x).
const(-A):- const(A).
const(A + B):- const(A), const(B).
const(A - B):- const(A), const(B).
const(A * B):- const(A), const(B).
const(A / B):- const(A), const(B).
const(A ^ B):- const(A), const(B).
const(root(A, B)):- const(A), const(B).

% Hilfsprädikate um Kommutativität zu gewährleisten
% (Vertauschung von Summanden und Faktoren)
swap(A * B, R):- 
	(swap(A, R1), swap(B, R2)),
	(R = R1 * R2; R = R2 * R1).

swap(A + B, R):- 
	(swap(A, R1), swap(B, R2)),
	(R = R1 + R2; R = R2 + R1).

swap(A / B, R):- swap(A, R1), swap(B, R2), R = R1 / R2.

swap(A ^ B, R):- swap(A, R1), swap(B, R2), R = R1 ^ R2.

swap(sin(A), R):- swap(A, R1), R = sin(R1).
swap(cos(A), R):- swap(A, R1), R = cos(R1).
swap(ln(A), R):- swap(A, R1), R = ln(R1).
swap(abs(A), R):- swap(A, R1), R = abs(R1).
swap(root(A, B), R):- swap(B, R1), R = root(A, R1).
swap(A, A).

%%%%%%%%%%%%%%%%%%%%%%
% Grundintegrale
%%%%%%%%%%%%%%%%%%%%%%

i(N, R):- const(N), R = N * x, !.

i(x, (0.5) * (x ^ 2)):- !.

% konstante Potenz
i(x ^ N, R):- const(N), R = (x ^ (N + 1)) / (N + 1), !.

% konstanter Faktor
i(N * B, R):- const(N), i(B, R1), R = N * R1, !.

% Addition
i(A + B, R):- i(A, R1), i(B, R2), R = R1 + R2, !.

% Subtraktion
i(A - B, R):- i(A + (-1 * B), R), !.

% Division durch Konstante
i(A / N, R):- const(N), i(A, R1), R = (1 / N) * R1, !.

% konstanter Faktor im Nenner
i(A / (N * X), R):- const(N), i(A / X, R1), R = (1 / N) * R1, !.

% n / X
i(N / X, R):- const(N),  not(N = 1), i(1 / X, R1), R = N * R1, !.

% (n / X) * Y
i((N / X) * Y, R):- const(N), not(N = 1), i((1 / X) * Y, R1), R = N * R1, !.

% e ^ x
i(e ^ x, e ^ x):- !.

% 1 / x
i(1 / x, ln(abs(x))):- !.

% 1 / (x + n)
i(1 / (x + N), R):- const(N), R = ln(abs(x + N)), !.

% 1 / (x + n)^2
i(1 / ((x + N) ^ 2), R):- const(N), R = -1 * (1 / (x + N)), !.

% tan(x)
i(tan(x), -1 * ln(cos(x))):- !.

% sin²(nx)
i(sin(N * x) ^ 2, R):- const(N), R = (0.5 * x) - ((1 / (4 * N)) * sin((2 * N) * x)), !. 

% cos²(nx)
i(cos(N * x) ^ 2, R):- const(N), R = (0.5 * x) + ((1 / (4 * N)) * sin((2 * N) * x)), !.

% ln²(x)
i(ln(x) ^ 2, ((x * (ln(x) ^ 2)) - (2 * (x * ln(x)))) + (2 * x)):- !.

% sin(nx) * cos(nx)
i(sin(N * x) * cos(N * x), R):- const(N), R = (1 / (2 * N)) * (sin(N * x) ^ 2), !.

% 1 / (sin(nx) * cos(nx))
i(1 / (sin(N * x) * cos(N * x)), R):- const(N), R = (1 / N) * ln(tan(N * x)), !.

% e^(ax) * sin(bx)
i((e ^ (N * x)) * sin( M * x), R):- const(N), const(M),
	R = ((e ^ (N * x)) / (N ^ 2 + M ^ 2)) * ((N * sin(M * x)) - (M * cos(M * x))), !.

% e^(ax) * cos(bx)
i((e ^ (N * x)) * cos( M * x), R):- const(N), const(M),
	R = ((e ^ (N * x)) / (N ^ 2 + M ^ 2)) * ((N * cos(M * x)) + (M * sin(M * x))), !.

% x * sin(nx)
i(x * sin(N * x), R):- const(N), R = ((1 / (N ^ 2)) * sin(N * x)) - ((x / N) * cos(N * x)), !.

% x * cos(nx)
i(x * cos(N * x), R):- const(N), R = ((1 / (N ^ 2)) * cos(N * x)) + ((x / N) * sin(N * x)), !.

% 1 / root(2, x)
i(1 / root(2, x), 2 * root(2, x)):- !.

% 1 / root(3, x)
i(1 / root(3, x), (3 / 2) * root(3, x ^ 2)):- !.

% e ^(nx)
i(e ^ (N * x), R):- const(N), R = (1 / N) * e ^ (N * x), !.

% xe^(nx)
i(x * e ^(N * x), R):- const(N), R = (((N * x) - 1) / N ^ 2) * e ^ (N * x), !.

% ln(x)
i(ln(x), (x * ln(x)) - x):- !.

% xln(x)
i(x * ln(x) , (x ^2) * ((ln(x) / 2) - (1 / 4))):- !.

% -n/(x^(n+1))
i((-1 * N) / (x ^ (N + 1)), R):- const(N), R = 1 / (x ^ N), !.

% -n/(x^(n+1)) falls n eine reelle Zahl (keine Variable) ist
i((-1 * N) / X, R):- number(N), N1 is N + 1, X = x ^ N1, R = 1 / (x ^ N), !.

% 1 / (2 * sqrt(x))
i(1 / (2 * root(2, x)), root(2, x)):- !.

% 1 / n*root(n, x ^ (n - 1))
i(1 / (N * root(N, x ^ (N + -1))), R):- const(N), R = root(N, x), !.

% 1 / n*root(n, x ^ (n - 1)) falls n eine reelle Zahl (keine Variable) ist
i(1 / (N * root(N, x ^ N1)), R):- number(N), N1 is N - 1, R = root(N, x), !.

% n^x * ln(n)
i((N ^ x) * ln(N), R):- const(N), R = N ^ x, !.

% (1 / ln(n)) * (1 / x)
i((1 / ln(N)) * (1 / x), R):- const(N), R = log(N, x), !.

% cos(x)
i(cos(x), sin(x)):- !.

% sin(x)
i(sin(x), -1 * cos(x)):- !.

% 1 / (cos(x)²)
i(1 / (cos(x) ^ 2), tan(x)):- !.

% 1 / (sin(x)²)
i(1 / (sin(x) ^ 2), -1 * cot(x)).

% 1 / root(2, 1 - x²)
i(1 / root(2, (1+  -(x ^ 2))), arcsin(x)):- !.

% -1 / root(2, 1 - x²)
i((-1) / root(2, (1+  -(x ^ 2))), arccos(x)):- !.

% 1 / 1 + x²
i(1 / (1 + (x ^ 2)), arctan(x)):- !.

% -1 / 1 + x²
i((-1) / (1 + (x ^ 2)), arccot(x)):- !.

% cosh(x)
i(cosh(x), sinh(x)):- !.

% sinh(x)
i(sinh(x), cosh(x)):- !.

% 1 / cosh(x)²
i(1 / (cosh(x) ^ 2), tanh(x)):- !.

% 1 / sinh(x)²
i(1 / (sinh(x) ^ 2), -1 * coth(x)):- !.

% 1 / root(2, x² + 1)
i(1 / root(2, (x ^ 2) + 1), arsinh(x)):- !.

% 1 / root(2, x² - 1)
i(1 / root(2, (x ^ 2) + -1 ), arcosh(x)):- !.

% f' / f
i(X / Y, R):- inte(X, R1), R1 = Y, R = ln(abs(Y)), !.

% root(2, x² + a²)
i(root(2, (x ^ 2) + (N ^ 2)), 0.5 * ((x * root(2, (x ^ 2) + (N ^ 2))) + (N ^ 2) * arsinh(x / N))):- const(N), !.

% root(2, x² - a²)
i(root(2, (x ^ 2)+ -(N ^ 2)), 0.5 * ((x * root(2, (x ^ 2)+ -(N ^ 2)))+ -(N ^ 2) * arcosh(x / N))):- const(N), !.

% root(2, a² - x²)
i(root(2, (N ^ 2)+ -(x ^ 2)), 0.5 * ((x * root(2, (N ^ 2)+ -(x ^ 2)))+ -(N ^ 2) * arcsin(x / N))):- const(N), !.

% führt swap für Eingegebene Formel aus um sie in eine integrierbare Form zu bringen
% fügt Integrationskonstante C an
inte(A, R):-
	swap(A, R1),
	i(R1, R2), R = R2 + 'C', !.

in C++ würd ich mir da gleich nen strick nehmen...

einen vereinfacher könnte man im grunde nach dem gleichen prinzip bauen.
wirklich die einfachste form zu finden ist dabei natürlich nicht ganz einfach (ist das überhaupt theoretisch gelöst?). womöglich die elemente des terms zählen und so lang suchen bis man die kürzeste lösung hat...

Ben04

Interessant, ich war mir gar nicht bewusst, dass man Prolog so einsetzen kann. Danke, da hab ich etwas hinzu gelernt.

Jedoch, hast du das eigentliche Problem geschickt umgangen und gar nicht erst gelöst: Das eigentliche Problem ist ja gerade die Vereinfachung und nicht das rechnen an sich. Ich hab jetzt noch keine Integration implementiert, einfach da dies vom mathematischen Standpunkt her nicht trivial ist (dein Programm löst auch nur die einfachen Fälle). Das Differenzieren ist aber bereits drin (neue Version) und da hat dein Prologprogram keinen wirklichen Vorteil da es das gleiche mit anderer Syntax ist:

struct derive_visitor:
	public boost::static_visitor<Expression>{

	Expression operator()(const Num::Rational&)const{
		return 0;
	}

	Expression operator()(const InvalidSubExpr&)const{
		return 0;
	}

	Expression operator()(const Parameter&param)const{
		if(param.name == var)
			return 1;
		else
			return 0;
	}

	Expression operator()(const Power&power)const{
		return power.exp*pow(power.base, power.exp-1)*derive(power.base, var);
	}

	Expression operator()(const Sum&sum)const{
		Expression new_sum;
		foreach(const Expression&i, sum)
			new_sum += derive(i, var);
		return new_sum;
	}

	Expression operator()(const Product&prod)const{
		Product b_prod = prod;
		b_prod.pop_front();
		Expression b = kill_small_prod(b_prod);
		Expression a = prod.front();
		Expression 
			da = derive(a, var), 
			db = derive(b, var);
		return a*db + da*b;
	}

	derive_visitor(const std::string&var):
		var(var){}

	const std::string&var;
};

Expression derive(const Expression&expr, const std::string&var){
	return boost::apply_visitor(derive_visitor(var), expr.root());
}

Viel mehr als Formel anwenden ist das auch nicht.

Interessant fände ich ein Beispiel wo Prologs Backtracking Algorithmus wirklich zum tragen kommt, zum Beispiel ein Programm zur Faktorisation das praktisch nur mit Formeln aus kommt und auch verschachtelte Anwendungen korrekt behandelt. Zum Beispiel:
a^2 + 6a - 7
-> a^2+6a+9 - 16
-> (a+3)^2-16
-> (a+3-4)(a+3+4)
-> (a-1)(a+7)
(Man könnte hier natürlich auch Delta rechnen allerdings würde das das Problem nicht lösen, spätestens bei trigonometrischen Ausdrücken ist mit solchen Tricks Schluss.)
Der problematische Schritt ist in meinen Augen der von -7 zu +9-16, es gibt einfach zu viele Möglichkeiten um -7 zu zerlegen um mit Backtracking weiter zu kommen.