(ns expresso-tutorial.simp-solve
(:use [numeric.expresso.core]))This section of the tutorial covers the advanced manipulation expresso provides for mathematical expressions. These include:
- evaluating constant subexpressions
- fully multiplying out an expression
- simplifying expressions
- transforming it to polynomial normal form
- differentiating an expression
- rearranging an equation to an unknown
- solving one equation or sets of simultaneous equations
From these manipulations, the solving is by far the most sophisticated transformation. This section will cover briefly the simpler transformations and will explore the solving capabilities. It also provides a practical section where expresso is used to solve word problems and to analyse roots and extremata of expressions.
These manipulations does a little bit more than just evaluating an expression if it contains no free variables. It also recognizes opportunities to fold constants if multiple of them occur in an associative or commutative operator:
(in-ns 'expresso-tutorial.simp-solve)
(evaluate-constants (ex (+ 1 2))) ;=> 3
;;expresso knows, that + is commutative, so it can fold 1 2 and 3 to 6
(evaluate-constants (ex (+ 1 x 2 3))) ;=> (+ 6 x)
;;it also folds successive constants in associative operations
(evaluate-constants (ex (inner-product x [[1 2][3 4]] [[5 6][7 8]])))
;=> (inner-product x [[19 22] [43 50]])Fully multiplying out an equation is also a useful manipulation if you explore your expressions at the repl to see what is really going on. Here are a few examples:
(in-ns 'expresso-tutorial.simp-solve)
(multiply-out (ex (* (+ a b) c))) ;=> (+ (* a c) (* b c))
(multiply-out (ex (** (+ a b c) 2)))
;=> (+ (** c 2) (* 2 b c) (** b 2) (* 2 a c) (* 2 a b) (** a 2))Simplify does a best heuristic approach to make the expression ‘simpler’. Simplifying is maybe the mathematical term which is not really defined. So simplify takes a heuristic approach to transform the expression to rules which make it simpler. In some unfortunate cases, simplify can make the expression even larger or more ‘complicated’ in some sense of the word. To get some control about the simplification process, simplify accepts a keyword argument :ratio which is the maximal ratio of simplified/original- expression which can come out of simplify. If the ratio is not reached, simplify fails returning nil.
(in-ns 'expresso-tutorial.simp-solve)
;;simplify folds constants
(simplify (ex (* a 3 4))) ;=> (* 12 a)
;;repeated applications of + and * are merged
(simplify (ex (+ (+ a b) (* c (* d e)) (+ f g)))) ;=> (+ f g a b (* d e c))
;;it recognizes special constants for operations
(simplify (ex (+ 0 (* 0 b) (* 1 b) (** c 1) (/ d 1) (- e 0)))) ;=> (+ b c d e)
;;and can simplify the inverses
(simplify (ex (+ (- a a) (- (* 2 a) a) (+ a (* -2 a)) (/ a a) (* a b (/ a)))))
;;=> (+ 1.0 b)Expresso also has some support for Polynomials and uses internally a recursive representation of univariate polynomials. It’s manipulations have special support for the case of univariate polynomials. An example for the solver: If all the equations which are given to the solver are polynomials with determined coefficients, it can build a matrix on that and solve the matrix with gaussian elimination. This function here transforms the given input to the recursive normalform of univariate polynomials with the speficied symbol as main variable:
(in-ns 'expresso-tutorial.simp-solve)
(to-polynomial-normal-form 'x (ex (+ (** (+ x 1) 2) (* a x))))
;;=> (+ 1 (* (+ 2 a) x) (** x 2))The differentiate function can differentiate a function with regard to a variable. You can also specify multiple variables in which case the funciton is differentiated one time for each symbol in the symbol vector
(in-ns 'expresso-tutorial.simp-solve)
(differentiate '[x] 'x) ;=> 1
(differentiate '[x] (ex (* (+ x 1) (+ x 2)))) ;=> (+ (* 2 x) 3)
(differentiate '[x] (ex (exp (exp x)))) ;=> (* (exp (exp x)) (exp x))
(differentiate '[x] (ex (+ (* 2 (** x 3)) (* 4 (** x 5)))))
;;=> (+ (* 6 (** x 2)) (* 20 (** x 4)))
(differentiate '[x x] (ex (+ (* 2 (** x 3)) (* 4 (** x 5)))))
;;=> (+ (* 12 x) (* 80 (** x 3)))
(differentiate '[x x x] (ex (+ (* 2 (** x 3)) (* 4 (** x 5)))))
;;=> (+ 12.0 (* 240 (** x 2)))
(differentiate '[x x x x] (ex (+ (* 2 (** x 3)) (* 4 (** x 5)))))
;;=> (* 480 x)
(differentiate '[x x x x x] (ex (+ (* 2 (** x 3)) (* 4 (** x 5)))))
;;=> 480.0
;;in case of multiple symbols, the order of the symbols is not important
;;(not a feature of the programming, but of mathematics ;))
(differentiate '[x y] (ex (* (** x 2) (** y 2))))
;;=> (* 4 y x)
(differentiate '[y x] (ex (* (** x 2) (** y 2))))
;;=> (* 4 x y)
The function rearrange takes an expression and the unknown and , if the equation contains only one occurrence of the unknown returns a list of equations with the variable isolated on the left hand side.
(in-ns 'expresso-tutorial.simp-solve)
;;rearrange is a purly syntactical process, so no simplifications and other
;;manipulations are done except from the rearrangeing. In the simple case there
;;is only one way how to rearrange the equation.
(rearrange 'x (ex (= (+ 1 x) 3))) ;=> ((= x (- 3 1)))
;;but there can be more than one
(rearrange 'x (ex (= (** x 2) 4)))
;;=> ((= x (** 4 (/ 2))) (= x (- (** 4 (/ 2)))))
(map simplify (rearrange 'x (ex (= (** x 2) 4)))) ;=> ((= x 2.0) (= x -2.0))
(rearrange 'x (ex (= (abs x) y))) ;=> ((= x y) (= x (- y)))
Now we come to the equation solver of expresso. It is by now the most sophisticated transformation and can solve an expression for one variable and also multiple expressions for multiple variables. The expressions can contain arbitrary other symbols. The result is a set of possible values/expressions that are solutions for x.
You can solve a single equation for an unknown ‘x by the following call to solve: (solve ‘x equation) it also acceppts a one element vector or set as the first argument. Let’s see how the solver performs on some examples:
(in-ns 'expresso-tutorial.simp-solve)
(solve 'x (ex (= (+ 1 x) 3))) ;=> #{2}
(solve 'x (ex (= (* 0 x) 1))) ;=> #{} there is no solution
(solve 'x (ex (= (* 0 x) 0))) ;=> _0 every value of x is a solution.
(solve 'x (ex (= (+ (* 3 x) 1) (* 2 x)))) ;=> #{-1}The solver is able to solve nearly all example equations on this site In the following are more examples given which demonstrate a solving method which the solver uses.
(in-ns 'expresso-tutorial.simp-solve)
;;expresso recognizes that the following expression is basically a polynomial
;;by noting that (** 2 (* 2 x)) is the same as (** (** x 2) 2) and that
;;(** 2 (+ x 1)) can also be rewritten to (* 2 (** 2 x)).
;;It then rewrites the expression to a polynomial of the main variable
;;(** 2 x) and then soles the equation by sustituton of (** 2 x)
(solve 'x (ex (= (+ (** 2 (* 2 x)) (- (* 5 (** 2 (+ x 1)))) 16) 0))) ;=> #{1 3}
;;expresso recignizes here, that all occurrences of the unknown ar in the
;;exponent of 100, so it can solve the equation by substitution of
;;(+ (** x 2) (* -6 x) 1)
(solve 'x (ex (= (+ (** 100 (+ (** x 2) (* -6 x) 1)) 5) 10)))
;;=> #{5.889547542811505 0.11045245718849461}
;;in this equation, expresso sees that the occurrences of the unknown are
;;inside of logs, so it chooses a solving strategy to eliminate all enclosing
;;log terms by recursively rearranging to a log term and exp it. The resulting
;;(polynomial) equation is then solved normally.
(solve 'x (ex (= (+ (log (- x 2)) (log (- (* 2 x) 3))) (* 2 (log x))))) ;=> #{6}Building on top of the single equation solve, expresso has the facility to solve multiple simultaneous equations for unknowns. If expresso can transform the system to a real matrix, it can use it’s build in gauss solver for this system. If not, it has a general equation solver which is based on solving one equation after another, substituting the partial solutions on the way like one would do by hand. Here are some examples:
(in-ns 'expresso-tutorial.simp-solve)
;;for multiple equations, solve takes a vector of symbols to solve for and
;;multiple equations. The output format is a set of solutions where the solution
;;consists of a map from the symbols to its values.
(solve '[x y z] (ex (= z (* 2 x))) (ex (= y (+ x z))) (ex (= x [1 2 3])))
;;=> #{{z [2 4 6], y [3 6 9], x [1 2 3]}}
;;you can specify only the symbols you care about
(solve '[y] (ex (= z (* 2 x))) (ex (= y (+ x z))) (ex (= x [1 2 3])))
;;=> #{{y [3 6 9]}}
;;expresso can form a matrix out of this set of equations and solve it using the
;;gaussian algorithm
(solve '[x y]
(ex (= (+ (* 3 x) (* 4 y)) 100))
(ex (= (- x y) 20))) ;=> #{{y 40/7, x 180/7}}
;;it can also solve system with arbitrary parameters by normal substitution
;;mechanism. In this set of equations, one equation is solved for one variable
;;and the result is substituted in the other variable, making it possible to
;;solve the equation. The result is then substituted back, so that the solutions
;;of the variables contain no other variables which are solved for.
(solve '[x y] (ex (= (+ (* a x) y) 7)) (ex (= (- (* b x) y) 1)))
;;=> #{{y (+ 7 (* -8 (/ (+ b a)) a)), x (* 8 (/ (+ b a)))}}
Let’s now use expresso’s facilities to solve actual problems. I hope that the examples demonstrate how simple it is to do symbolic manipulations with expresso.
We will use expresso here to solve five word problems from this site: Question 1A:
A third grade teacher had a box of pencils to use as prizes for her students. If 1/10 of the pencils are green, 1/2 of them are white, 1/4 of them are blue and the remaining 45 pencils are red, what is the number of blue pencils?
There are easier ways to extract equations from the text but for demonstration purposes the equations will be almost mechanically extracted from the text. The following snippet shows how this expressions can be solved with expresso.
(in-ns 'expresso-tutorial.simp-solve)
(solve 'blue
(ex (= pencils (+ green white blue red)))
(ex (= (/ pencils 10) green))
(ex (= (/ pencils 2) white))
(ex (= (/ pencils 4) blue))
(ex (= red 45))) ;=> #{{blue 75N}}Question 2A:
If Jill’s age is increased by Mark’s age, the result is 2 times Jill’s age 5 years ago. If Mark is now M years old, what is Jill’s present age in terms of M?
This translates straightforward to one equation which expresso can then solve:
(in-ns 'expresso-tutorial.simp-solve)
(solve 'j (ex (= (+ j m) (* 2 (- j 5))))) ;=> #{(+ 10 m)}Question 3A:
8 Carpenters worked from 7:00 am until 4:00 pm framing a house. Working at the same rate, how many additional carpenters would be needed for the job to hae take 3 hours less?
This is a little bit harder to translate to formulas. First the different units in time have to be translated, so that the time difference is (- 16 7) hours Also for this word problem, the rate has to be considered and there is a reciprocal relationship between number of workers and time until the work is done. Having realized that, it is straightforward to build the equations and expresso solves them.
(in-ns 'expresso-tutorial.simp-solve)
(solve '[additional]
(ex (= time (- 16 7)))
(ex (= carpenters 8))
(ex (= rate (* time carpenters)))
(ex (= (/ rate (+ additional carpenters)) (- time 3))))
;;=> #{{additional 4N}}Question 4A
Sara left a rest stop at 10:00 am and drove north on the interstate at a rate of 60 miles per hour. Todd left an hour later and headed south at a rate of 50 miles per hour. At what time were Sara and Todd 225 miles apart?
This word problem involes two movements in different directions which start at different times and move with different speeds. The total difference is there- fore the sum of the two distances. All that is needed is to express the formulas for the distances traveled by each in dependence on the time, with the total distance set to 225.
(in-ns 'expresso-tutorial.simp-solve)
(solve 'time
(ex (= start-sara 10))
(ex (= speed-sara 60))
(ex (= start-todd (+ start-sara 1)))
(ex (= speed-todd 50))
(ex (= distance-sara (* (- time start-sara) speed-sara)))
(ex (= distance-todd (* (- time start-todd) speed-todd)))
(ex (= (+ distance-sara distance-todd) 225))) ;=> #{{time 25/2}}
Excercise for the reader: What happens, if you let the total distance unspecified eg by replacing the 255 in the last equation above by a variable?
Question 5A:
Tori owes her friend b dollars. Last month she paid 1/4 of the amount owed. This month she paid her friend 1/5 of the remaining amount plus $15.00. In terms of b, how much money does she still owe?
The difficulty in this question if the stepwise reduction of the remaining depth. With expresso it is easy to just add another equation to the set.
(in-ns 'expresso-tutorial.simp-solve)
(solve '[remaining2 original]
(ex (= original b))
(ex (= remaining1 (- original (/ original 4))))
(ex (= remaining2 (- remaining1 (+ (/ remaining1 5) 15)))))
;=> #{{remaining2 (+ -15N (* 3/5 _0)), original _0}}In this second example we want to do use expresso to do symbolic analysis of functions in regard to a variable. Below is a short snippet of code which shows how expresso can be used to find out properties of functions.
(in-ns 'expresso-tutorial.simp-solve)
(defn roots
"returns the set of roots of the expression in regard to var"
[var expr]
(solve var (ex (= ~expr 0))))
(defn extremata
"gets the extrema of the expression in regard to var. Returns a map with the
keys :maxima and :minima"
[var expr]
(let [d1 (differentiate [var] expr)
d2 (differentiate [var] d1)
candidates (roots var d1)]
(if (seq candidates)
(let [extremata
(->> candidates
(map (fn [candidate] [candidate (evaluate d2 {var candidate})]))
(remove #(== 0 (second %)))
(group-by #(< 0 (second %))))]
{:maxima (map first (get extremata false))
:minima (map first (get extremata true))}))))
(defn analyse-function
"returns a map with the :roots, the :maxima and the :minima of the expression
in regard to var"
[var expr]
(assoc (extremata var expr)
:roots (roots var expr)))
(analyse-function 'x (ex (- (** x 4) (** x 2))))
;=> {:roots #{0 -1 1},
;; :maxima (0),
;; :minima (0.7071067811865476 -0.7071067811865476)}
Let’s see how the analyse-function works. The root function just solves for the values of the variable for which the expression is zero. The function extremata uses the root function and the function differentiate to get the local maxima and minima of the function. We will step through the function with the example (ex (- (** x 4) (** x 2))). The first thing to do is to create the first and the second derivative of the function. Because local extrema represent the points of the graph where it changes from sinking to rising or the other way round, the graph must have a slope of zero in this point. Hence the candidates for extrema are the points where the first derivative of the expression is zero - the roots of the first derivative.
(in-ns 'expresso-tutorial.simp-solve)
(def expr (ex (- (** x 4) (** x 2))))
(differentiate '[x] expr) ;=> (+ (* 4 (** x 3)) (- (* 2 x)))
(differentiate '[x x] expr) ;=> (+ (* 12 (** x 2)) -2.0)
(roots 'x (ex (+ (* 4 (** x 3)) (- (* 2 x)))))
;;=> #{0 0.7071067811865476 -0.7071067811865476}These are only candidates because there can be points where the derivative is zero, but the graph doesn’t change direction. The easiest example of that is the graph of x**3. We must therefore test if the graph really changes direction in the candidates. That means that the sign of the slope has to change in this point. And this means that the slope of the slope can’t be zero. In mathematical terms, the test is that the second derivative of the expression is not zero at the candidate point. We can test that the second derivative is not zero with the function evaluate and pass it the map from ‘x to the result
(in-ns 'expresso-tutorial.simp-solve)
(def candidates (roots 'x (ex (+ (* 4 (** x 3)) (- (* 2 x))))))
candidates ;=> #{0 0.7071067811865476 -0.7071067811865476}
(map #(evaluate (ex (+ (* 12 (** x 2)) -2.0)) {'x %}) candidates)
;;=> (-2.0 4.000000000000002 4.000000000000002)
Wee see that all our candidates are actually extremata. Now the last job is to differentiate - pun intendet - between maxima and minima. This can be done with the following reasoning: If we have a maximum, the graph of the expression changes from rising to falling. This means, that the slope starts above zero, gradually gets lower, reaches zero at the maximum and then goes below zero when the graph begins sinking. That means that the slope is constantly sinking, what means that the slope of the slope - the second derivative - is below zero. So the candidates for which the second derivative is negative are the maxima and the candidates for which it is positive are the minima.