n;;; -*- Mode:Common-Lisp; Base:10 -*- ;; Written by: Richard J. Fateman ;; File: integrate.lisp ;; (c) 199 Richard J. Fateman "Design: Figure that all the cleverness of the algorithmic programs has been included in the preprocessing before this stage. IN particular, the problems left for this program have not succumbed to the simple derivative divides program other parts of Moses' SIN scheme the Risch algorithm and extensions as available has failed. There are really 2 parts of this problem, quite separable. The indefinite "antiderivative" problem, and the definite integration problem. We can also try to segment this into integration of a function of strictly a single variable (no parameters), and other functions. A function of a single variable is a lot easier, especially since we don't really have a very good handle of functions of several complex variables. Since we rely on pattern matching, we must make sure that the time to find a match is only a weak function of the number of patterns in the data base. If the data base doubles, the match time should not go from t to 2t, but perhaps from t to t+1. Indefinite integrals: Heuristic substitutions for change of variable in expression E1 Find the n deepest nested subexpression. call them u1, u2, ...un. with u1 being the deepest non-atomic expression containing the variable of integration x. (should we exclude linear ax+b ?) It could be as simple as u1=x^2. in general u=f(x), invertible to x=g(u) / with side conditions.. Let E2 be the result of replacing in E1, (and limits), f(x)--> u, and everywhere there occurs some h(x), replace with h(g(u)); replace dx by d(g(u)). See if E2 is simpler -- has lower maximum depth of nested than E1 -- and if so, (or even if not) try to integrate it instead. Problems. 1.The form of the derivative d(g(u)) can be critical. See the problems with (say) Bessel functions, where the result has many variations. Even with trig functions, the simplicity of E2 may depend critically on subtle simplifications like Sin(ArcCos...).. 2. Maximum Depth isn't a great measure. arcsinh(x) may be worse than 1/(x^2+1). Some level of "transcendence" may be needed. 3. Non terminating heuristic, generally. 4. Solve for inverse may provide multiple values and/or restrictions " ;; this is a odd function... we are trying to get a plausible ;; collection of subexpressions to use for a change of variables ;; from *var* to some newvar. (defun depthrank(tree *var* &aux *ans*) (declare (special *var* *ans*)) "return a list of sub-expressions {s[i]} of tree, each depending on *var*, indexed and sorted by how deep s[i] is in the tree." (dr tree 0) ;; top level (tree itself) is 0 (sort *ans* #'(lambda(r s)(> (car r)(car s)))) ;;debug ;; (mapc #'(lambda(r) (format t "~s~%" r)) *ans*) *ans* ) (defun dr(tree n) (declare (special *var* *ans*p)) (cond ((atom tree) (return-from dr nil)) ((depends-on *var* tree) (push(list n tree) *ans*))) (mapcar #'(lambda(z) (dr z (1+ n))) tree)) (defun depends-on(v tr) "true if v occurs in the tree tr anywhere" (cond ((eq v tr)t) ((atom tr) nil) (t (or (depends-on v (car tr))(depends-on v (cdr tr)))))) (setq m '(+ (* A B E) E (* C (^ D E)))) (setq n '(+ y z (* 2 x)(+ (sin x) 1) (sin(+ (cos x) (* h theta))))) (defun changevar(e new fold) "in the integral e replace occurrences of oldvar by new=fold" ;; example changevar( integrate(sin(x),x,0,a) , u, sin(x)) ;; yields integrate(u/sqrt(1-u^2),u,0,sin(a)) ;; macsyma does this with changevar('integrate(sin(x),x),sin(x)=u,u,x);