Hi...
I'm looking for a lisp routine that will do symbolic differentiation
of a function, given (obviously) an expression in prefix notation and what
variable it is being differentiated against... Something like
(differentiate '(* x x)) => (* 2 x)
Obviously that's a simple homework assignment... But, what I need it for
is to do these functions:
power
+,*,-,/
Exp (Although, perhaps I don't need Exp, I can just use (pow E X)
Log... I dunno what I'm going to do about this function tho... Hmmm
But, I need Erf (The error function) But, I suppose, derivative of
Erf is easy enough, to encode... Actually, I can live with it,
if it doesn't differentiate Erf out the box...
Here's what I want to do.
I want to integrate a function
(Exp[((Log[X1/X0]-m)/sd)^2/2] Log[a X1 + b])/X1
(/ (* (exp (/ (pow (/ (- (log (/ X1 X0)) m) sd) 2) 2)) (log (+ (* a X1) b))) X1)
(It's the PDF of a lognormal distributed X1 from X0 * log of a linear
function of X1...)
(The actual function is a little more complicated, but, this is
the basic idea)
I'm hoping to try to use genetic programming to create a function who's
derivative is the function above... Is this feasible? Is this a good way
to approach this problem of mine? So, the fitness criteria would be
how far off the generated function is from the one I'm asking for...
(But, first, I'd like some equivalent of freshmeat for open sourced stuff
or cpan for perl stuff for lisp... Does such a beast exist?)
Thanks!
Binesh Bannerjee
--
"The measure of love is what one is willing to give up for it." --
Geoffrey Fielding - "Pandora and the Flying Dutchman"
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)
From: Alex Gittens
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <opr2lc2lcwxm2pxo@news.ev1.net>
On 30 Jan 2004 07:53:56 GMT, Binesh Bannerjee
<······························@hex21.com> wrote:
> I'm hoping to try to use genetic programming to create a function who's
> derivative is the function above... Is this feasible? Is this a good way
> to approach this problem of mine? So, the fitness criteria would be
> how far off the generated function is from the one I'm asking for...
>
> (But, first, I'd like some equivalent of freshmeat for open sourced stuff
> or cpan for perl stuff for lisp... Does such a beast exist?)
>
Perl stuff for LISP?
For Scheme code, which may or may not be easily translated to LISP,
there's JACAL. Then there's also a LISP mockup of Mathematica (cf.
http://http.cs.berkeley.edu/~fateman/mma.mailer -- the download url is in
the message).
The genetic programming idea sounds weird (searching an infinite
dimensional space with a finite number of genes), but I suppose it's
feasible provided you don't expect an exact symbolic antiderivative, and
you have the right functions in your genetic space. But then, I don't know
much about genetic programming, so my opinion is moot. In any case, I'd be
interested to know how you set that up.
Alex
--
From: Friedrich Dominicus
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <87llnphnov.fsf@fbigm.here>
Check out chapter 8 of Paradigms of Artificial Intelligence
Programming from Peter Norvig.
Regards
Friedrich
From: Marco Antoniotti
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <PwwSb.8$xV.879@typhoon.nyu.edu>
Friedrich Dominicus wrote:
> Check out chapter 8 of Paradigms of Artificial Intelligence
> Programming from Peter Norvig.
>
Unless you want polynomial GCD's :)
Marco
Friedrich Dominicus wrote:
> Check out chapter 8 of Paradigms of Artificial Intelligence
> Programming from Peter Norvig.
Shh. Now there's nothing left for him to do :-)
While Binesh waits for his copy of PAIP, he could
warm up with:
<http://mitpress.mit.edu/sicp/full-text/sicp/book/node39.html>
--
Jens Axel S�gaard
Binesh Bannerjee <······························@hex21.com> writes:
> (But, first, I'd like some equivalent of freshmeat for open sourced stuff
> or cpan for perl stuff for lisp... Does such a beast exist?)
<http://www.cliki.net>
<http://www.cliki.net/asdf-install>
Binesh Bannerjee wrote:
> Hi...
> I'm looking for a lisp routine that will do symbolic differentiation
> of a function, given (obviously) an expression in prefix notation and what
> variable it is being differentiated against... Something like
> (differentiate '(* x x)) => (* 2 x)
The routine is "d", in the code below.
(defun d(e v)(if(atom e)(if(eq e v)1 0)
(funcall(or(get(car e)'d)#'undef)e v)))
(defun undef(e v)`(d,e,v))
(defun r(op s)(setf(get op'd)(compile()`(lambda(e v)(let((x(cadr e)))
(list'*(subst x'x',s)(d x v)))))))
(r'cos'(* -1(sin x)))
(r'sin'(cos x))
(r'exp'(exp x))
(r'log'(expt x -1))
(setf(get'+'d)#'(lambda(e v)`(+,@(mapcar #'(lambda(r)(d r v))(cdr e)))))
(setf(get'*'d)
#'(lambda(e v)`(*,e(+,@(mapcar #'(lambda(r)`(*,(d r v)(expt,r -1)))(cdr
e))))))
(setf(get'expt'd)#'(lambda(e v)`(*,e,(d`(*,(caddr e)(log,(cadr e)))v))))
For an explanation, see
http://www.cs.berkeley.edu/~fateman/papers/deriv.pdf
>
> Obviously that's a simple homework assignment... But, what I need it for
> is to do these functions:
> power
> +,*,-,/
> Exp (Although, perhaps I don't need Exp, I can just use (pow E X)
> Log... I dunno what I'm going to do about this function tho... Hmmm
> But, I need Erf (The error function) But, I suppose, derivative of
> Erf is easy enough, to encode... Actually, I can live with it,
> if it doesn't differentiate Erf out the box...
You will have to add 1 line.
>
> Here's what I want to do.
> I want to integrate a function
> (Exp[((Log[X1/X0]-m)/sd)^2/2] Log[a X1 + b])/X1
> (/ (* (exp (/ (pow (/ (- (log (/ X1 X0)) m) sd) 2) 2)) (log (+ (* a X1) b))) X1)
>
> (It's the PDF of a lognormal distributed X1 from X0 * log of a linear
> function of X1...)
>
> (The actual function is a little more complicated, but, this is
> the basic idea)
>
> I'm hoping to try to use genetic programming to create a function who's
> derivative is the function above... Is this feasible?
Not really, unless you like exponential, and possibly non-terminating
search.
Is this a good way
> to approach this problem of mine? So, the fitness criteria would be
> how far off the generated function is from the one I'm asking for...
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.
>
> (But, first, I'd like some equivalent of freshmeat for open sourced stuff
> or cpan for perl stuff for lisp... Does such a beast exist?)
You mean a collection of programs written in lisp like the CMU AI archive?
>
> Thanks!
> Binesh Bannerjee
>
>
Good luck. Maybe you will come up with some better ideas in the future.
In comp.lang.lisp Richard Fateman <········@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)
From: Joe Marshall
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <hdydlz4b.fsf@comcast.net>
Binesh Bannerjee <······························@hex21.com> writes:
> 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.
For the sake of curiosity, how does Mathematica compare to Macsyma in
it's ability to integrate this sort of thing?
Mathematica's inability to
find a closed form for an integral does not mean that the integral
cannot be expressed in closed form.
You can study the various
components of the Risch integration procedure which in some
ways provides a decision for integrability, but that is subject
to the ability to simplify expressions. This latter task
turns out to be undecidable for even a modestly complicated domain
(Daniel Richardson, 1968), so even if Mathematica "implemented
the Risch 'algorithm'" it might not solve a problem posed in an
unanticipated form.
It would probably also be a mistake to believe that the Risch
methods are fully implemented in Mathematica, though this
might change from time to time. Integration of special functions
(like erf) might not use these methods anyway.
so: if Mathematica can't do an integral in closed form, all you
can conclude is that it can't do that integral in closed form.
And if you simplified it differently, perhaps it could do the
integral then. Or not.
Same for Macsyma and Maple and Axiom and Reduce and Mupad and...
RJF
Joe Marshall wrote:
> Binesh Bannerjee <······························@hex21.com> writes:
>
>
>>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.
>
>
> For the sake of curiosity, how does Mathematica compare to Macsyma in
> it's ability to integrate this sort of thing?
Richard Fateman <········@sbcglobal.net> writes:
<snip>
> to the ability to simplify expressions. This latter task
> turns out to be undecidable for even a modestly complicated domain
<snip>
> Same for Macsyma and Maple and Axiom and Reduce and Mupad and...
>
> RJF
I take it that the "and..." followed by "RJF" means that you disagree
with Penrose on humans not being bound by Godel's theorems? :-)
--
Use of tools distinguishes Man from Beast. And UNIX users from WINDOZE lusers.
Richard Fateman (········@sbcglobal.net) wrote:
: Mathematica's inability to
: find a closed form for an integral does not mean that the integral
: cannot be expressed in closed form.
: You can study the various
: components of the Risch integration procedure which in some
: ways provides a decision for integrability, but that is subject
: to the ability to simplify expressions. This latter task
: turns out to be undecidable for even a modestly complicated domain
: (Daniel Richardson, 1968), so even if Mathematica "implemented
: the Risch 'algorithm'" it might not solve a problem posed in an
: unanticipated form.
Daniel Richardson result is an artifact of his definition of equalty of
expressions. If you take different definition of equality (used by Risch)
and add an assumption about numbers ("no unexpected equalities between
transcendental numbers") then equality of elementary functions is decidable.
The needed assumption is a long standing open problem.
: It would probably also be a mistake to believe that the Risch
: methods are fully implemented in Mathematica, though this
: might change from time to time. Integration of special functions
: (like erf) might not use these methods anyway.
: so: if Mathematica can't do an integral in closed form, all you
: can conclude is that it can't do that integral in closed form.
: And if you simplified it differently, perhaps it could do the
: integral then. Or not.
The main point is that Risch methods have very high complexity, so
even full implementation is expected to run out of resources. On
the other hand one can have four results:
i) integral done
ii) out of resources
iii) proven lack of elementary antiderive
iv) lack of elementary antiderive if the number theoretic assumption is true
Unfortunatly, Mathematica (and other programs) does not tell which of
ii), iii) or iv) holds.
Of course non-elementary functions like erf make things more complicated,
but if lump lack of apropriate algorithm with lack of resources then still
you have four outcames.
--
Waldek Hebisch
·······@math.uni.wroc.pl
From: Richard Fateman
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <401D4E70.2030401@sbcglobal.net>
Waldek Hebisch wrote:
> Richard Fateman (········@sbcglobal.net) wrote:
> : Mathematica's inability to
> : find a closed form for an integral does not mean that the integral
> : cannot be expressed in closed form.
>
> : You can study the various
> : components of the Risch integration procedure which in some
> : ways provides a decision for integrability, but that is subject
> : to the ability to simplify expressions. This latter task
> : turns out to be undecidable for even a modestly complicated domain
> : (Daniel Richardson, 1968), so even if Mathematica "implemented
> : the Risch 'algorithm'" it might not solve a problem posed in an
> : unanticipated form.
>
> Daniel Richardson result is an artifact of his definition of equalty of
> expressions. If you take different definition of equality (used by Risch)
> and add an assumption about numbers ("no unexpected equalities between
> transcendental numbers") then equality of elementary functions is decidable.
1. Assuming something that you do not know is true is not the way to
resolve questions about decidability.
> The needed assumption is a long standing open problem.
2. I believe you are referring to Schanuel's conjecture, but there is no
expectation that this resolution will be easy.
3. I do not know what you mean about different definitions of equality,
but it would be appropriate for one newsgroup, sci.math.symbolic, to
elaborate. There are certainly issues like is (x-1)/(x^2-1) = 1/(x+1)
considering what happens at x=-1 or x=1. There are also functions that
are constant, but not necessarily the same constant, like
atan(x)+atan(1/x). Its derivative is zero, so it must be a constant.
Which constant depends on whether x>0 or x<0.
There are functions that are zero except at an infinite number of points.
4. Integration in terms of elementary functions, or elementary functions
extended by some set of additional functions defined by integrals, is
essentially a parlor trick. The real question of interest to people
using or building computer algebra systems is generally (a) definite
integration, perhaps symbolic in parameters, or (b) can you find a form
for the integral in terms of ANY expression, not just "elementary".
I've written (actually, to sci.math.symbolic) on why Risch integration
is not 'the solution' to this, interesting as it may seem to theoreticians.
>
>.. snip...
>
> The main point is that Risch methods have very high complexity, so
> even full implementation is expected to run out of resources.
Why do you say this? Do you have any evidence from some benchmarks
from some computer algebra systems that suggest they bog down because
they are doing some integration using the Risch algorithm? I have
never heard of any. People do not tend to integrate "arbitrarily large"
integrands, and so asymptotic analysis is not particularly important.
Even if it were, I see no reason to think that the load on
resources should be especially worse than many other computations that
are routinely performed on small to moderate expressions.
This is not to say it easy. For example, sparse polynomial division
worst case takes exponential time. Divide (x^(1000)-1) by (x+1). You
get 1000 terms.
In general, a division with input of size O(n) can produce O(10^n) terms.
So what? We don't say, "Don't do division, it can run out of resources"
> the other hand one can have four results:
>
> i) integral done
> ii) out of resources
> iii) proven lack of elementary antiderive
> iv) lack of elementary antiderive if the number theoretic assumption is true
>
> Unfortunatly, Mathematica (and other programs) does not tell which of
> ii), iii) or iv) holds.
(v) Error in implementation resulting in an incorrect integral.
(vi) Error in implementation resulting in failure to integrate.
(vii) Incomplete implementation of Risch algorithm so integral not found
(this is likely to be something the program can report!)
(viii) {QUITE LIKELY, I THINK} Failure of the related simplification
routines to find appropriate differential field extensions in which to
express the integrand thereby displaying the appropriate algebraic
independence, and hence failing, even though an answer might exist.
(ix) integral done, but in a form so peculiar as to be useless for any
further work, using (say) complex exponentials and algebraics when
elementary functions like cos and tan would do.
>
> Of course non-elementary functions like erf make things more complicated,
> but if lump lack of apropriate algorithm with lack of resources then still
> you have four outcames.
Most programmers would not lump "stack overflow" with "I forgot to write
the program"
If there are further responses I suggest they go to sci.math.symbol only.
>
> --
> Waldek Hebisch
> ·······@math.uni.wroc.pl
From: Joe Marshall
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <3c9uebo7.fsf@comcast.net>
Richard Fateman <········@sbcglobal.net> writes:
> There are functions that are zero except at an infinite number of points.
That's a rather broad exception.
--
~jrm
Joe Marshall <·············@comcast.net> wrote:
+---------------
| Richard Fateman <········@sbcglobal.net> writes:
| > There are functions that are zero except at an infinite number of points.
|
| That's a rather broad exception.
+---------------
I suspect Fateman may have been referring to some particularly weird
functions of measure zero, that is, whose integrals are zero over any
finite interval, yet which also contain an infinite number of non-zero
values over any finite interval, yet no value is negative. [We had to
construct some in my sophomore topology seminar (long, long ago)...]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Simple examples exist, e.g. the function f, defined on the reals by
f(x) = 1 if x is rational
f(x) = 0 otherwise
Alex
Rob Warnock wrote:
> Joe Marshall <·············@comcast.net> wrote:
> +---------------
> | Richard Fateman <········@sbcglobal.net> writes:
> | > There are functions that are zero except at an infinite number of points.
> |
> | That's a rather broad exception.
> +---------------
>
> I suspect Fateman may have been referring to some particularly weird
> functions of measure zero, that is, whose integrals are zero over any
> finite interval, yet which also contain an infinite number of non-zero
> values over any finite interval, yet no value is negative. [We had to
> construct some in my sophomore topology seminar (long, long ago)...]
>
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
>
Alex McGuire <····@alexmcguire.com> wrote:
+---------------
| Rob Warnock wrote:
| > I suspect Fateman may have been referring to some particularly weird
| > functions of measure zero...
|
| Simple examples exist, e.g. the function f, defined on the reals by
| f(x) = 1 if x is rational
| f(x) = 0 otherwise
+---------------
Yeah, stuff like that.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Not so weird as you might think.
You can construct functions like this:
Consider S:= arctan(sin(x))+arctan(1/(sin(x))).
try plotting this and you will see it is a square function with
an infinite number of zeros (where the derivative is undefined).
If you integrate it with Mathematica 4.1 you get a function which
is identically 0. This is incorrect, but it might very well
come out of the Risch algorithm, according to the specs of Risch.
Why is it wrong? On most intervals the definite integral is not zero.
Also, if you compute the derivative, you should get back something
equivalent to arctan(sin(x))+arctan(1/(sin(x))), but of course you
get 0 for the derivative of 0.
I have added sci.math.symbolic to the cross posting for this,
since it isn't really a lisp question, is it?
(A function which is zero {nearly everywhere} except for an infinite
number of points is the derivative of S.)
RJF
Alex McGuire wrote:
> Simple examples exist, e.g. the function f, defined on the reals by
>
> f(x) = 1 if x is rational
> f(x) = 0 otherwise
>
> Alex
>
> Rob Warnock wrote:
>
>> Joe Marshall <·············@comcast.net> wrote:
>> +---------------
>> | Richard Fateman <········@sbcglobal.net> writes:
>> | > There are functions that are zero except at an infinite number of
>> points.
>> | | That's a rather broad exception.
>> +---------------
>>
>> I suspect Fateman may have been referring to some particularly weird
>> functions of measure zero, that is, whose integrals are zero over any
>> finite interval, yet which also contain an infinite number of non-zero
>> values over any finite interval, yet no value is negative. [We had to
>> construct some in my sophomore topology seminar (long, long ago)...]
>>
>>
>> -Rob
>>
>> -----
>> Rob Warnock <····@rpw3.org>
>> 627 26th Avenue <URL:http://rpw3.org/>
>> San Mateo, CA 94403 (650)572-2607
>>
>
Daniel Lichtblau (private email) politely questioned what
I had written about what I had done in Mathematica last night.
Mathematica actually gets a fine answer to the question
posed below, essentially the same step-function S, times x.
(By contrast, Commercial Macsyma gives "atan2(0,0) generated" and (free)
Maxima returns the input expression unchanged. Maple 7 also
declines to do it. So Mathematica is the winner here.)
What I tried to integrate was D, the DERIVATIVE of S wrt x,
which is zero except in those infinitely-many places where
sin(x)=0, when D should not be zero. (But Mathematica thinks it is).
I suppose a reasonable value for that integral is 0 (plus
a constant). Unfortunately, in this case the constant seems
to change an infinite number of times, and it depends on x.
Anyway, the point was to illustrate the creation of functions
that are infinitely problematical without having to define
functions that magically detect distinctions between rational
and non-rational numbers. The derivative of S is such a function.
RJF
Richard Fateman wrote:
> Not so weird as you might think.
>
> You can construct functions like this:
>
> Consider S:= arctan(sin(x))+arctan(1/(sin(x))).
>
> try plotting this and you will see it is a square function with
> an infinite number of zeros (where the derivative is undefined).
>
> If you integrate it with Mathematica 4.1 you get a function which
> is identically 0. This is incorrect, but it might very well
> come out of the Risch algorithm, according to the specs of Risch.
>
^^^ wrong
<snip>
RJF
Richard Fateman <·······@cs.berkeley.edu> wrote:
> Daniel Lichtblau (private email) politely questioned what
> I had written about what I had done in Mathematica last night.
>
> Mathematica actually gets a fine answer to the question
> posed below, essentially the same step-function S, times x.
> (By contrast, Commercial Macsyma gives "atan2(0,0) generated" and (free)
> Maxima returns the input expression unchanged. Maple 7 also
> declines to do it. So Mathematica is the winner here.)
I agree that Mathematica's antiderivative is technically correct.
However, it is not continuous, and that leads to an incorrect answer
from Mathematica:
In[1]:= Integrate[ArcTan[Sin[x]] + ArcTan[1/Sin[x]], {x, a, b}]
Out[1]= -a*ArcTan[Csc[a]]+b*ArcTan[Csc[b]]-a*ArcTan[Sin[a]]+b*ArcTan[Sin[b]]
The answer above is obtained in an obvious way from Mathematica's
antiderivative, but is incorrect if an integer multiple of Pi lies
between a and b:
In[2]:= %/.{a -> 0, b -> 2*Pi}
Out[2]= Indeterminate
In[3]:= %%/.{a -> -Pi/2, b -> 3*Pi/2}
Out[3]= -Pi^2
The two results above should both be 0. Thankfully Mathematica knows
that they should be 0 when specific values are given for the limits of
integration. For example:
In[4]:= Integrate[ArcTan[Sin[x]] + ArcTan[1/Sin[x]], {x, 0, 2*Pi}]
Out[4]= 0
But that does not excuse, IMO, the fact that Mathematica's definite
integral from a to b is incorrect.
So now perhaps you're wondering what sort of antiderivative I'd like.
Well, I'd like one that's continuous, such as
Pi/2 * (-1)^Floor[x/Pi] * (x - Pi/2 - Pi*Floor[x/Pi])
Using such an antiderivative, F(x), the definite integral from a to b is
always given correctly by F(b) - F(a).
BTW, the antiderivative above has another advantage over Mathematica's:
it does not require the evaluation of trig and inverse trig functions.
David Cantrell
> What I tried to integrate was D, the DERIVATIVE of S wrt x,
> which is zero except in those infinitely-many places where
> sin(x)=0, when D should not be zero. (But Mathematica thinks it is).
>
> I suppose a reasonable value for that integral is 0 (plus
> a constant). Unfortunately, in this case the constant seems
> to change an infinite number of times, and it depends on x.
>
> Anyway, the point was to illustrate the creation of functions
> that are infinitely problematical without having to define
> functions that magically detect distinctions between rational
> and non-rational numbers. The derivative of S is such a function.
>
> RJF
>
> Richard Fateman wrote:
> > Not so weird as you might think.
> >
> > You can construct functions like this:
> >
> > Consider S:= arctan(sin(x))+arctan(1/(sin(x))).
> >
> > try plotting this and you will see it is a square function with
> > an infinite number of zeros (where the derivative is undefined).
> >
> > If you integrate it with Mathematica 4.1 you get a function which
> > is identically 0. This is incorrect, but it might very well
> > come out of the Risch algorithm, according to the specs of Risch.
> >
> ^^^ wrong
> <snip>
> RJF
From: Joe Marshall
Subject: Re: LISP routines to do symbolic differentiation
Date:
Message-ID: <ptcxc9zi.fsf@comcast.net>
····@rpw3.org (Rob Warnock) writes:
> Joe Marshall <·············@comcast.net> wrote:
> +---------------
> | Richard Fateman <········@sbcglobal.net> writes:
> | > There are functions that are zero except at an infinite number of points.
> |
> | That's a rather broad exception.
> +---------------
>
> I suspect Fateman may have been referring to some particularly weird
> functions of measure zero, that is, whose integrals are zero over any
> finite interval, yet which also contain an infinite number of non-zero
> values over any finite interval, yet no value is negative. [We had to
> construct some in my sophomore topology seminar (long, long ago)...]
Probably.
My bank account has a million dollars except at an infinite number of times....
--
~jrm
On Sat, 31 Jan 2004 06:44:07 +0000, Richard Fateman wrote:
> so: if Mathematica can't do an integral in closed form, all you can
> conclude is that it can't do that integral in closed form. And if you
> simplified it differently, perhaps it could do the integral then. Or not.
>
> Same for Macsyma and Maple and Axiom and Reduce and Mupad and...
Didn't the Axiom documentation claim for Axiom to have a complete
implementation of Risch's algorithm? If memory serves well, the assertion
in that documentation was that if Axiom is not able to do an integral in
closed form then it has effectively proved that it can't be done.
Jim Ford wrote:
.
>
>
> Didn't the Axiom documentation claim for Axiom to have a complete
> implementation of Risch's algorithm? If memory serves well, the assertion
> in that documentation was that if Axiom is not able to do an integral in
> closed form then it has effectively proved that it can't be done.
According to a message in sci.math.symbolic newsgroup, 2003-09-05 from
Manuel Bronstein "Re: Integration capabilities"
this is not what Axiom does.
Axiom will sometimes
return a message indicating you have reached an unimplemented branch
of the algorithm.
Also note that "can't be done" is an incorrect phrase. You must add
"in terms of elementary functions". So if the answer is a Bessel
function, it "can't be done" this way.
>
On Mon, 02 Feb 2004 09:42:51 -0800, Richard Fateman wrote:
>
>
> Jim Ford wrote:
> .
>>
>>
>> Didn't the Axiom documentation claim for Axiom to have a complete
>> implementation of Risch's algorithm? If memory serves well, the
>> assertion in that documentation was that if Axiom is not able to do an
>> integral in closed form then it has effectively proved that it can't be
>> done.
>
> According to a message in sci.math.symbolic newsgroup, 2003-09-05 from
> Manuel Bronstein "Re: Integration capabilities" this is not what Axiom
> does.
>
> Axiom will sometimes
> return a message indicating you have reached an unimplemented branch of
> the algorithm.
I.e. the algorithm has not been completely implemented, correct?
> Also note that "can't be done" is an incorrect phrase. You must add "in
> terms of elementary functions". So if the answer is a Bessel function, it
> "can't be done" this way.
Right. I was thinking "in terms of elementary functions" all along. Isn't
this constraint an explicit element of Risch's algorithm, anyway?
Binesh Bannerjee <······························@hex21.com> wrote in message news:<························@news.rcn.com>...
> In comp.lang.lisp Richard Fateman <········@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
In comp.lang.lisp Daniel Lichtblau <····@wolfram.com> wrote:
[deleted]
> 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).
Right... (I have 4.2, unfortunately can't quite afford the upgrade just
yet, but, your telling me that it can solve certain things that 4.2 can't
will definitely make me start saving up more! Thanks!)
But, the reason why I needed to have it integrate from -Infinity to Infinity,
is because, (in that instance) I have to compute the 5th moment of the function
overall, so I need it from -Infinity to Infinity... Basically, if you
look at
http://www.hex21.com/~binesh/mathematica_oddity/index.html
at the top, you'll see what I did... I made a polynomial adjustment
to Exp[-z^2/2]/Sqrt[2Pi] * polynomial(z) such that
Integrate[f(z),{z,-Infinity,Infinity} == 1
Integrate[f(z)*z,{z,-Infinity,Infinity} == 0
Integrate[f(z)*z^2,{z,-Infinity,Infinity} == 1
Integrate[f(z)*z^3,{z,-Infinity,Infinity} == skewness
Integrate[f(z)*z^4,{z,-Infinity,Infinity} == kurtosis
and ask mathematica to solve for the coefficients of the polynomial...
Mathematica does that as you can see from that url...
> 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}]]]
It's _slightly_ off.. X1 should go from {X1,lo,hi} and the Assumptions would be
{X0>0,X1>0,(a*lo+b)>0,(a*hi+b)>0,sd>0,Im[m]==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).
Well, no, the genetic programming, is just a means to an end... What I
need is to integrate that function... Actually tho, the function
with the polynomial correction for skewness and kurtosis... How it's
solved... I don't really care that much... The trouble is that numerical
integration of that integral is taking way too long for me... That's why
I'm looking to symbolically integrate it... (It takes too long, because,
this is actually a simpler version, the real problem involves multiple
X's, so it looks like
F[n_,regions_] := Sum[Integrate @@
Join[{Product[PDF[0, 1, sk, ku,
(Log[Subscript[X, i]/Subscript[X, i - 1]] -
Subscript[m, i])/Subscript[sd, i]]/
(Subscript[X, i]*Subscript[sd, i]), {i, 1, n}]*
Log[1 + Sum[Subscript[a, i]*Subscript[X, j, i] +
Subscript[b, i], {i, 1, n}]]},
Table[{Subscript[X, i], Subscript[lo, j, i],
Subscript[hi, j, i]}, {i, 1, n}]], {j, 1, regions}]
for different n's, and j's, with n ranging fairly small (1-7) but j ranging
from (2-10000 or more) (I guess j has no upper limit really)
I was hoping to symbolically integrate it to speed up the calculation
is all...
(PDF[0,1,sk,ku,Z] is the normal pdf times a polynomial chosen
such that
Integrate[PDF[0,1,sk,ku,Z]*Z^2,{Z,-Infinity,Infinity}]==sk and
Integrate[PDF[0,1,sk,ku,Z]*Z^3,{Z,-Infinity,Infinity}]==ku
Thanks!
Binesh
> Daniel Lichtblau
> Wolfram Research
--
"I have here in my hand a list of 205, a list of names made known to the
secretary of state as being members of the Communist Party and who
nevertheless are still working and shaping policy in the State Department."
-- Senator Joseph McCarthy
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)
Binesh Bannerjee <······························@hex21.com> wrote in message news:<·························@news.rcn.com>...
> Hi...
> I'm looking for a lisp routine that will do symbolic differentiation
> of a function ...
Have you checked http://sourceforge.net/projects/maxima/ ?