Lower-level poor man's integrator
Jon Harrop
Manuel Bronstein's "Poor Man's Integrator" is a simple symbolic integrator
written in just 95 lines of Maple code:
http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/
However, it relies upon some non-trivial Maple-specific CA functions.
I would like to translate this into a general purpose (non-CAS) language.
Thus, I would like to know of any free software that can evaluate the
existing Maple code and whether or not any translations to general purpose
languages (particularly OCaml, F#, Scala, Standard ML or Haskell) exist?
I am aware of Wolfram Research's translation to Mathematica:
http://emmy.cnnet.upr.edu/lmedina/software/software_index.html
Although this is several times longer and more obfuscated it doesn't
actually seem to be any lower level: it still relies upon Mathematica's own
CA functions such as Together and TrigToTan as well as LinearSolve.
--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
Waldek Hebisch
It should be easy to eliminate Maple (or Mathematica) specific
functions. But you need general-purpose CAS operations:
- Arithmetic on multivariate polynomials (addition, multiplication,
exact division and GCD).
- Some polynomial utilities like finding variables, substitution,
rearraging term order...
- Fractions of polynomials (rational functions) and solver for systems
of linear equations with polynomial coefficients.
- Way to represet functions that you want to integrate as rational
functions, for exaple "kernels". In particular you need way
to compute derivatives.
I would say that any system containing needed operation deserves
to be calles a CAS (possibly a "Poor Man's CAS"). Also, core of
the method is described in Bronstein's book about integration,
AFAICS working from the book should be easier than working
from Bronstein's code.
--
Waldek Hebisch
heb...@math.uni.wroc.pl
Richard Fateman
....
> Thus, I would like to know of any free software that can evaluate the
> existing Maple code and whether or not any translations to general purpose
> languages (particularly OCaml, F#, Scala, Standard ML or Haskell) exist?
pmint can be (and has been) written as a brief Maxima (Macsyma program)
and probably also in Axiom. Each of these can convert the program into
more-or-less standard Common Lisp, with calls to appropriate subroutines.
As Waldek Hebisch correctly points out, you cannot seriously consider an
implementation of pmint unless you can represent in your system the
expressions you propose to integrate, most likely as a tree, as well as
a number of standard "CAS" operations on such trees. You probably also
want to read and print such expressions.
clicl...@freenet.de
Jon Harrop schrieb:
To what extent can pmint handle algebraic integrands?
Martin.
A N Niel
> To what extent can pmint handle algebraic integrands?
>
> Martin.
" pmint is a very short (95 lines) Maple program for integrating
transcendental elementary or special functions. "
The examples include some rational functions, but all the rest are
transcendental.
Axel Vogt
http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/examples/
do not treat those
Having Maple I would be more interested in versions covering
parametric cases (and I remember vaguely a guy from Linz did
that by translating & extending it in MMA).
clicl...@freenet.de
Axel Vogt schrieb:
> do not treat those
>
> Having Maple I would be more interested in versions covering
> parametric cases (and I remember vaguely a guy from Linz did
> that by translating & extending it in MMA).
Oh, it cannot even deal with integrands involving parameters. And the
absence of algebraic examples probably means that it cannot handle such
integrands either. My initial interest in preparing a Derive version has
dropped to almost-zero.
Martin.
Richard Fateman
> Axel Vogt schrieb:
>> clicl...@freenet.de wrote:
>>> To what extent can pmint handle algebraic integrands?
>>>
>> http://www-sop.inria.fr/cafe/Manuel.Bronstein/pmint/examples/
>> do not treat those
>>
>> Having Maple I would be more interested in versions covering
>> parametric cases (and I remember vaguely a guy from Linz did
>> that by translating & extending it in MMA).
>
> Oh, it cannot even deal with integrands involving parameters. And the
> absence of algebraic examples probably means that it cannot handle such
> integrands either.
I expect that both of these restrictions are false.
My initial interest in preparing a Derive version has
> dropped to almost-zero.
But you would probably be disappointed by the performance (speed).
>
> Martin.
Christopher Creutzig
> To what extent can pmint handle algebraic integrands?
I'm not sure about the extent to which Bronstein's implementation can,
but the method itself (i.e., the Risch-Norman algorithm for parallel
integration) works just fine (as far as heuristics go) on algebraic
integrands if you simply treat them as transcendentals. Which is also a
reasonable way to get a surprisingly large number of antiderivatives for
algebraic integrands from the Risch algorithm, by the way.
For both algorithms, the correctness of results is not affected by the
misrepresentation of algebraics as transcendentals. What does break down
is the Risch algorithm's proof of non-integrability, and you can find
equivalent inputs some of which can be integrated and other cannot.
Christopher
clicl...@freenet.de
Richard Fateman schrieb:
>
> clicl...@freenet.de wrote:
> >
> > Oh, it cannot even deal with integrands involving parameters. And the
> > absence of algebraic examples probably means that it cannot handle
> > such integrands either.
>
> I expect that both of these restrictions are false.
>
> > My initial interest in preparing a Derive version has
> > dropped to almost-zero.
>
> But you would probably be disappointed by the performance (speed).
>
... ok, I have retrieved the Maple code from the trash bin ...
Martin.
Axel Vogt
Certainly Christopher Creutzig knows much more about that than
me, but I think it it is (partially) intended for special cases
(Risch-Norman algorithm) which Maple could not cover and from
95 lines ~ 3/2 pages of code one should not expect everything.
Christopher Creutzig
> me, but I think it it is (partially) intended for special cases
> (Risch-Norman algorithm) which Maple could not cover and from
> 95 lines ~ 3/2 pages of code one should not expect everything.
The Risch-Norman algorithm is actually a fascinating piece of
machinery. (I'm using MuPAD syntax, since that is what I have around all
the time, but the principles are obviously system agnostic.)
Let's assume we define elliptic functions E and K. For what follows,
the only thing we need is that they know how to be differentiated, so
I'll not write any code beyond that:
ellipE := funcenv(ellipE):
ellipK := funcenv(ellipK):
ellipE::diff :=
proc(f, x)
local z;
begin
z := op(f);
(ellipE(z) - ellipK(z))/(2*z) * diff(z, x);
end_proc:
ellipK::diff := proc(f,x)
local z;
begin
z := op(f);
(ellipE(z) - (1-z)*ellipK(z))/
(2*(1-z)*z) * diff(z, x);
end_proc:
What can we do with this code? Obviously, creating Taylor series, and
once ellipE and ellipK also learned to be evaluated at 0, those would
also have useful coefficients. But with the Risch-Norman algorithm, the
definition above is sufficient for a couple of symbolic integrations, too!
>> int(ellipE(x), x)
2 ellipE(x) 2 ellipK(x) / 2 ellipE(x) 2 ellipK(x) \
----------- - ----------- + x | ----------- + ----------- |
3 3 \ 3 3 /
>> diff(%, x)
2 ellipE(x) 2 ellipK(x) / ellipE(x) - ellipK(x)
----------- + ----------- + x | --------------------- -
3 3 \ 3 x
ellipE(x) + ellipK(x) (x - 1) \ ellipE(x) - ellipK(x)
----------------------------- | + --------------------- +
3 x (x - 1) / 3 x
ellipE(x) + ellipK(x) (x - 1)
-----------------------------
3 x (x - 1)
>> simplify(%)
ellipE(x)
>> int(x*ellipE(x), x)
8 ellipE(x) 8 ellipK(x) 2 / 2 ellipE(x) 2 ellipK(x) \
----------- - ----------- + x | ----------- + ----------- | +
45 45 \ 5 15 /
/ 2 ellipE(x) 2 ellipK(x) \
x | ----------- + ----------- |
\ 45 45 /
Christopher
Axel Vogt
> On 2/19/10 10:18 PM, Axel Vogt wrote:
>
>> me, but I think it it is (partially) intended for special cases
>> (Risch-Norman algorithm) which Maple could not cover and from
>> 95 lines ~ 3/2 pages of code one should not expect everything.
>
> The Risch-Norman algorithm is actually a fascinating piece of
> machinery. (I'm using MuPAD syntax, since that is what I have around all
> the time, but the principles are obviously system agnostic.)
>
> Let's assume we define elliptic functions E and K. For what follows,
> the only thing we need is that they know how to be differentiated, so
> I'll not write any code beyond that:
>
> ellipE := funcenv(ellipE):
> ellipK := funcenv(ellipK):
>
> ellipK::diff := proc(f,x) ...
< Axel Vogt: snipped some parts>
>
> What can we do with this code? Obviously, creating Taylor series, and
> once ellipE and ellipK also learned to be evaluated at 0, those would
> also have useful coefficients. But with the Risch-Norman algorithm, the
> definition above is sufficient for a couple of symbolic integrations, too!
>
>>> int(ellipE(x), x)
>>> simplify(%)
>
> ellipE(x)
>
<Axel Vogt: again snipped some parts ...>
This is a bit too short for me: do you say, that Mupad does
find that *only* through defining the differentiation and
knowing evaluation in 0, using the Risch-Norman algorithm ?
Christopher Creutzig
> Christopher Creutzig wrote:
>> What can we do with this code? Obviously, creating Taylor series, and
>> once ellipE and ellipK also learned to be evaluated at 0, those would
>> also have useful coefficients. But with the Risch-Norman algorithm, the
>> definition above is sufficient for a couple of symbolic integrations, too!
>>
>>>> int(ellipE(x), x)
>>>> diff(%, x)
>>>> simplify(%)
> >
>> ellipE(x)
> >
> <Axel Vogt: again snipped some parts ...>
>
> This is a bit too short for me: do you say, that Mupad does
> find that *only* through defining the differentiation and
> knowing evaluation in 0, using the Risch-Norman algorithm ?
I'm saying that MuPAD finds these integrals with the Risch-Norman
algorithm only through definition of the derivatives. The code I sent
was everything my computer was told about ellipE and ellipK, which are
not predefined names in MuPAD. I only defined diff(ellipE(f(x)), x) and
diff(ellipK(f(x)), x), and *nothing else*.
Obviously, for this to work, taking derivatives has to stop introducing
new functions after a few steps. For example, if you define
diff(besselJ(v, x), x) = v/x*besselJ(v, x) - besselJ(v + 1, x) and not
tell the system how to rewrite besselJ to reduce the index v, the
Risch-Norman algorithm will not be able to build its differential field
to work in. But unlike the Risch algorithm, it does not require a simple
field tower and thus can work with functions like the elliptic integrals
I used as an example above, Lambert's W function (which the Risch
algorithm does not handle because its derivative is not polynomial), etc.
Christopher