Expression Simplification

Question

J'ai ce code pour calculer les dérivés:

(define (diff x expr) 
    (if (not (list? expr)) 
    (if (equal? x expr) 1 0) 
    (let ((u (cadr expr)) (v (caddr expr))) 
    (case (car expr) 
     ((+) (list '+ (diff x u) (diff x v))) 
     ((-) (list '- (diff x u) (diff x v))) 
     ((*) (list '+ 
        (list '* u (diff x v)) 
        (list '* v (diff x u)))) 
     ((/) (list ‘div (list '- 
        (list '* v (diff x u)) 
        (list '* u (diff x v))) 
        (list '* u v))) 
)))) 

Comment puis-je simplifier les expressions algébriques?

au lieu de x + x montrent 2x

et

au lieu de x * x montrent x^2

Answer 1

Peut-être this code de PAIP sera utile. C'est Common Lisp, qui est assez similaire à Scheme. Le point d'entrée est la fonction simp.

Notez qu'il utilise également this file.

Note historique: Le chapitre PAIP pertinent fait référence à Macsyma, le système d'algèbre informatique développé dans le MIT dans les années 1960, et a été la base de Mathematica, Maple (maintenant dans Matlab) et d'autres outils.

Answer 2

est ici un début:

Modifier la votre fonction dérivée de (define (diff x expr) ...) à quelque chose comme (define (simp expr) ...).

pour le x + x cas, faire quelque chose comme

(case (car expr) 
    ((+) (if (equal u v) ; check for identical subexpressions 
     `(* ,(simp u) 2) ; if u==v, simplify 2u 
     `(+ ,(simp u) ,(simp v)))) 
    ...) 

Le cas x * x devrait être similaire. Finalement, vous voudrez peut-être convertir le if en un cond si vous avez besoin de faire beaucoup de simplifications différentes.

Ceci est un problème difficile à résoudre complètement et les liens qu'offre eliben valent le coup d'œil.

Answer 3

La simplification des expressions algégraiques est assez difficile, surtout par rapport au calcul des dérivées. La simplification devrait être faite récursivement. Vous simplifiez les expressions les plus intimes en premier. N'essayez pas trop à la fois. Je commencerai par les plus élémentaires que simplifications par exemple:

0 + x -> x 
0 * x -> 0 
1 * x -> x 
x^0 -> 1 
x^1 -> x 

Remplacer la soustraction par addition et division par la multiplication

x - y -> x + (-1)*x 
x/y -> x^(-1) 

Cela peut ne pas sembler aussi une simplification, mais cela simplifiera votre code. Vous pouvez toujours inverser cette étape à la fin. Puis, vous utilisez l'associativité et la commutativité pour trier vos termes. Déplacer des valeurs numériques sur le côté gauche, trier les variables par un ordre prédéfini (il ne doit pas être alphabétique, mais il doit toujours être le même)

(x * y) * z -> x * (y * z) 
x * 2 -> 2 * x 
2 * (x * 3) -> 2 * (3 * x) 

Simplifier exposants de

(x^y)^z -> x^(y * z) 

Simplifiez la numérique les pièces.

2 * (3 * x) -> 6 * x 
2 + (3 + x) -> 5 + x 

Une fois cela fait, vous pouvez envisager de collecter des expressions courantes.

Answer 4

Le problème général est difficile, mais vous pouvez obtenir un long chemin avec une forme normale de somme de produits, représentée comme une carte finie de la clé (nom de la variable) au coefficient. Cette forme est idéale pour les équations linéaires et la résolution linéaire, et elle peut être étendue à la multiplication et aux pouvoirs sans trop de problèmes. Si vous définissez des "constructeurs intelligents" pour l'arithmétique sur ce formulaire, vous pouvez obtenir une différenciation symbolique raisonnable et résoudre l'équation en cours.

Ceci est un hack rapide, mais je l'ai utilisé dans quelques applications. Plusieurs cela a fonctionné dedans; quelques fois ce n'était pas assez bon. Pour quelque chose de plus sérieux, vous parlez des années de travail.

Si vous voulez des exemples de code, vous pouvez lire environ one of my equation solvers.