Expresion Simplification

Question

I have this code to calculate derivatives:

(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)))
))))

How can I simplify algebraic expressions?

instead of x + x show 2x

and

instead of x * x show x^2

Answer 1

Perhaps this code from PAIP will be useful. It's Common Lisp, which is quite similar to Scheme. The entry point is the simp function.

Note that it also uses this file.

Historical note: The relevant PAIP chapter refers to Macsyma, the computer algebra system developed in MIT in the 1960s, and was the basis for Mathematica, Maple (now in Matlab) and other tools.

Answer 2

Here's a start:

Change the your derivative function from (define (diff x expr) ...) to something like (define (simp expr) ...).

for the x + x case, do something like

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

The x * x case should be similar. Eventually you may want to convert the if into a cond if you need to do a lot of different simplifications.

This is a Hard Problem to solve completely and the links eliben gives are worth looking at.

Answer 3

Simplification of algegraic expressions is quite hard, especially compared to the computation of derivates. Simplification should be done recursively. You simplify the innermost expressions first. Don't try too much at a time. I'd start with the most basic simplifications only e.g:

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

Replace subtraction by addition and division by multiplication

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

This may not look as a simplification, but it will simplify your code. You can always reverse this step at the end.

Then you use associativity and commutativity to sort your terms. Move numerical values to the left side, sort variables by some predefined order (it doesn't have to be alphabetical but it should always be the same)

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

Simplify exponents

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

Simplify the numerical parts.

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

Once you have done this you can think about collecting common expressions.

Answer 4

The general problem is hard, but you can get a long way with a sum-of-products normal form, represented as a finite map from key (variable name) to coefficient. This form is great for linear equations and linear solving, and it can be extended to multiplication and powers without too much trouble. If you define "smart constructors" for arithmetic on this form you can get some reasonable symbolic differentiation and equation solving going.

This is a quick hack, but I've used it in a few applications. Several it worked in; a couple times it wasn't good enough. For something more serious you're talking years of work.

If you want code examples you can read about one of my equation solvers.