Re: LISP routines to do symbolic differentiation

From: Daniel Lichtblau (danl_at_wolfram.com)
Date: 01/31/04 

Date: 31 Jan 2004 10:51:27 -0800

Binesh Bannerjee <binesh-dated-1076107557.be1784@hex21.com> wrote in message news:<401af4f2$0$2656$61fed72c@news.rcn.com>...
> In comp.lang.lisp Richard Fateman <rfateman@sbcglobal.net> wrote:
>
>
> > Binesh Bannerjee wrote:
>
> [Code and link deleted -- Thanks!]
>
> > You will have to add 1 line.
>
> Yep...
> (r 'erf '(/ (* 2 (exp (- (* x x)))) (sqrt(pi))))
>
> > And this fitness criterion is...?? How close is (x-1)*(x+1) to x^2-1?
> > This problem is known to be "recursively undecidable". Look it up.
>
>
> I understand... But, I've tried Mathematica to integrate the function I have,
> and it doesn't come back... I took that initially as meaning it was effectively
> unsolvable... BUT, I came up with a set of functions f(x)g'(x) such that
> f(x)g'(x) + f'(x)g(x) wouldn't symbolically integrate with Mathematica,
> if given in an appropriate form, but, would symbolically integrate if
> given in another form. (at least it terminates quick... This one
> didn't even terminate in one form, but, in another form, solved it
> pretty quickly...
> http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&threadm=ahtugt%24qnb%241%40smc.vnet.net&rnum=1&prev=/groups%3Fhl%3Den%26lr%3D%26ie%3DUTF-8%26oe%3DUTF-8%26selm%3Dahtugt%2524qnb%25241%2540smc.vnet.net
> )
>
> Anyhow, the specifics of f(X) and g'(X) that I mentioned above were
>
> f(X) =
> 4 3 X
> (3 (5 + ku) sd + 12 sd sk (m - Log[--]) -
> X0
>
> 2 X 2
> 6 (-3 + ku) sd (m - Log[--]) +
> X0
>
> X 4 X 3
> (-3 + ku) (m - Log[--]) + 4 sd sk (-m + Log[--]) )
> X0 X0
>
> 2 2
> (m - Log[X/X0]) /(2 sd ) 5
> / (24 E Sqrt[2 Pi] sd X)
>
> (Basically that same tweak to the pdf that I mentioned above)
>
> and g'(X) = Log[a X + b]
>
> Mathematica can't symbolically integrate this:
> ExpandAll(f(x)g'(x)+g(x)f'(x))
>
> (It can if, it's not expanded... But, the fact that it can't do it, spells
> to me, that it's _possible_ for a function that Mathematica claims to be
> unable to integrate, to in fact be integrable analytically.)
>
> I understand that nothing can absolutely guarantee an answer... But,
> in the specific case you mention, I think I could write something that
> would figure out that those two are the same... (the heuristic I'm thinking
> of would always _try_ to have the lowest precedence operator at the outermost
> lisp expression. So, always try to have sums of products...) In any case,
> whether or not the heuristic works, all I'm hoping for from the GP routine is
> a set of good _looking_ attempts... and, then I can decide if that gives me
> any extra direction is all.
>
> Here's the mathematica notebook at
> http://www.hex21.com/~binesh/mathematica_oddity/#relevant
>
> If all this still isn't a good way of symbolically integrating
> F1[X]DG1[X] (as defined in the link above), then I'd
> appreciate any pointers to some good way of doing so... (I've already
> tried Mathematica...)
>
> > You mean a collection of programs written in lisp like the CMU AI archive?
>
> Yep... Thanks again!
>
> > Good luck. Maybe you will come up with some better ideas in the future.
>
> I hope so!
>
> Binesh
>
>
>
> --
> "What do you know about hell? Would you like me to show you?"
> -- Lyta, Babylon 5
>
> PGP Key: http://www.hex21.com/~binesh/binesh-public.asc
> Key fingerprint = 421D B4C2 2E96 B8EE 7190 A0CF B42F E71C 7FC3 AD96
> SSH2 Key: http://www.hex21.com/~binesh/binesh-ssh2.pub
> SSH1 Key: http://www.hex21.com/~binesh/binesh-ssh1.pub
> OpenSSH Key: http://www.hex21.com/~binesh/binesh-openssh.pub
> CipherKnight Seals:
> http://www.hex21.com/~binesh/binesh-seal.tar.bz2.cs256
> http://www.hex21.com/~binesh/binesh-seal.zip.cs256
> http://www.hex21.com/~binesh/binesh-certificate.gif.cs256
> Decrypt with CipherSaber2 N=256, Password="WelcomeJedi!" (No quotes)

I confess I am a bit confused as to what exactly you did using
Mathematica. I'll make a few comments based on what I have seen in
this thread and the one at the URL given above.

First, at the URL you posted some definite integrals. These may use
methods other than indefinite integration, and moreover can spend time
attempting to assess conditions for convergence. Hence the timings may
have little to do with those of the corresponding indefinite
integrals. For example, you have:

ff[a_, b_, c_, d_, e_, f_, X_] := (a + b*X + c*X^2 + d*X^3 + e*X^4 +
f*X^5)*
    Exp[-(((X - m)/sd)^2)/2]/(Sqrt[2*Pi]*sd)

In the version I have (which I think behaves similarly to the current
street version), we get for the indefinite integral:

In[5]:= InputForm[Timing[Integrate[ff[a, b, c, d, e, f, X]*((X -
m)/sd)^5, x]]]

Out[5]//InputForm=
{0.4200000000000014*Second,
 -((x*(m - X)^5*(a + X*(b + X*(c + X*(d + X*(e + f*X))))))/
   (E^((m - X)^2/(2*sd^2))*Sqrt[2*Pi]*sd^6))}

For the definite integral:

In[6]:= InputForm[Timing[Integrate[ff[a, b, c, d, e, f, X]*((X -
m)/sd)^5,
  {X,-Infinity,Infinity}, Assumptions->sd>0]]]

Out[6]//InputForm=
{7.67*Second, 15*sd*(b + 2*c*m + m^2*(3*d + m*(4*e + 5*f*m)) +
   7*(d + 2*m*(2*e + 5*f*m))*sd^2 + 63*f*sd^4)}

Version 4.2 of Mathematica did indeed hang on this. But, as I noted,
this is unrelated to the behavior for the indefinite integral (which
works fine in that version).

For the integration in the present thread, I'm guessing you want to do
something like:

InputForm[Timing[Integrate[(Exp[((Log[X1/X0]-m)/sd)^2/2]*
  Log[a*X1 + b])/X1, {X1,1,X0},
  Assumptions->{sd>0,X0>1,Im[m]==0,a>0,b>0}]]]

First, I'll note that Mathematica does not do this particular
indefinite integration. As you and Richard Fateman both note, it may
well be the case that it can be done if the integrand given in some
different mathematically equivalent form. Moreover, as Richard Fateman
surmised, Mathematica does not have a full implementation of the Risch
method, hence one can indeed pose problems for which an elementary
antiderivative exists, but is not found by Mathematica (though often
the special function methods will find a non-elementary representation
in such cases).

For the definite integral posed above, Mathematica also does nothing
useful. Offhand I do not know if this indicates a bug or if the
integration is simply beyond the technology we have available. I plan
to look into it.

I'm not sure what exactly you have in mind to do from here. If it is
to find antiderivatives using genetic programming, it ain't gonna work
(but no need to take my word for that if you have available time and
want to try it out).

Daniel Lichtblau
Wolfram Research