patches for the calculus code
Wilfried_Huss
I have written some code for the Maxima interface.
You can find the patches at:
http://www.math.tugraz.at/~huss/sage
calculus1.patch implements the conversion from Maxima
matrices to Sage matrices.
calculus2.patch adds symbolic gamma and factorial functions.
(The factorial is named fact() so it doesn't clash with the
factorial in sage.rings.arith)
Finally calculus3.patch renames the symbolic factorial to factorial(),
and changes all imports of sage.rings.arith.factorial to
sage.calculus.calculus.factorial. I had to keep a renamed version
of the factorial function in sage.rings.arith to avoid circular
imports at startup.
The patches are against 3.2-alpha1, after applying all 3 patches
all tests passed.
Here is a sample session with the new functionality:
sage: var('x,y')
sage: v = maxima('v: vandermonde_matrix([x, y, 1/2])')
sage: v
matrix([1,x,x^2],[1,y,y^2],[1,1/2,1/4])
sage: type(v)
<class 'sage.interfaces.maxima.MaximaElement'>
sage: v.sage()
[ 1 x x^2]
[ 1 y y^2]
[ 1 1/2 1/4]
sage: mlist = maxima('[v, sin(x), 1, v.v]').sage()
sage: mlist
[[ 1 x x^2]
[ 1 y y^2]
[ 1 1/2 1/4],
sin(x),
1,
[ x^2 + x + 1 x*y + x^2/2 + x x*y^2 + 5*x^2/4]
[ y^2 + y + 1 3*y^2/2 + x y^3 + y^2/4 + x^2]
[ 7/4 y/2 + x + 1/8 y^2/2 + x^2 + 1/16]]
sage: [parent(i) for i in mlist]
[Full MatrixSpace of 3 by 3 dense matrices over Symbolic Ring,
Symbolic Ring,
Symbolic Ring,
Full MatrixSpace of 3 by 3 dense matrices over Symbolic Ring]
sage: gamma(x/2)(x=5)
3*sqrt(pi)/4
sage: f = factorial(x + factorial(y))
sage: maxima(f).sage()
factorial(factorial(y) + x)
sage: f(y=x)(x=3)
362880
I hope it is useful.
Greetings,
Wilfried Huss
William Stein
Thanks! Could you write to Michael Abshoff (<mabs...@googlemail.com>) and ask
for a trac account, then open three trac tickets, one
for each of the above? Thanks again!
William
mabshoff
On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:
> On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss
>
>
> <h...@finanz.math.tugraz.at> wrote:
>
> > Hi,
>
> > I have written some code for the Maxima interface.
> > You can find the patches at:
> > http://www.math.tugraz.at/~huss/sage
>
> > calculus1.patch implements the conversion from Maxima
> > matrices to Sage matrices.
pynac available for some of the basic symbolic manipulation tasks. It
is far from bullet proof, but it is a start, so the days of Maxima as
the default implementation of the low level symbolic stuff is coming
finally to an end :)
> > calculus2.patch adds symbolic gamma and factorial functions.
> > (The factorial is named fact() so it doesn't clash with the
> > factorial in sage.rings.arith)
symbolic code this could be useful.
> > Finally calculus3.patch renames the symbolic factorial to factorial(),
> > and changes all imports of sage.rings.arith.factorial to
> > sage.calculus.calculus.factorial. I had to keep a renamed version
> > of the factorial function in sage.rings.arith to avoid circular
> > imports at startup.
function even for integers which ought to be the most common use of
factorial. When the point counting code was using Maxima to compute
ceil, floor and sqrt the code as a whole was slower by a factor of
three which illustrates nicely why we don't want to use Maxima unless
there is a good reason to do so. Especially considering that using
mpfr's functions was abotu a million times faster since there is no
pexpect overhead. I could see using that code in case the argument is
non-integer, but not using the highly optimized gmp implementation for
something that is many orders of magnitude slower is just not what we
want to do.
Cheers,
Michael
William Stein
>
>
>
> On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:
>> On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss
>>
>
> Hi,
>
>>
>> <h...@finanz.math.tugraz.at> wrote:
>>
>> > Hi,
>>
>> > I have written some code for the Maxima interface.
>> > You can find the patches at:
>> > http://www.math.tugraz.at/~huss/sage
>>
>> > calculus1.patch implements the conversion from Maxima
>> > matrices to Sage matrices.
>
> This should come in handy, but starting with 3.2 we will finally have
> pynac available for some of the basic symbolic manipulation tasks. It
> is far from bullet proof, but it is a start, so the days of Maxima as
> the default implementation of the low level symbolic stuff is coming
> finally to an end :)
And I think we still want to have as many conversions between
Maxima and Sage as possible, even if Maxima isn't the default
backend for symbolic manipulation. It's still very good for
Maxima and Sage to be able to communicate. The more
capabilities for communication between Sage and other systems,
the better.
>
>> > calculus2.patch adds symbolic gamma and factorial functions.
>> > (The factorial is named fact() so it doesn't clash with the
>> > factorial in sage.rings.arith)
>
> Provided the factorial bit does not interfere with the current non-
> symbolic code this could be useful.
+1
>
>> > Finally calculus3.patch renames the symbolic factorial to factorial(),
>> > and changes all imports of sage.rings.arith.factorial to
>> > sage.calculus.calculus.factorial. I had to keep a renamed version
>> > of the factorial function in sage.rings.arith to avoid circular
>> > imports at startup.
>
> I don't like this patch at all since it forces us to use a Maxima
> function even for integers which ought to be the most common use of
> factorial.
I didn't look at the patch, but just want to comment that using
sage.calculus.calculus.factorial instead of sage.rings.arith.factorial
doesn't a priori imply that Maxima is used to compute factorials.
I.e., I could imagine an implementation where GMP is still used
for this:
sage: time n = factorial(10^6)
CPU times: user 1.90 s, sys: 0.10 s, total: 2.00 s
> When the point counting code was using Maxima to compute
> ceil, floor and sqrt the code as a whole was slower by a factor of
> three which illustrates nicely why we don't want to use Maxima unless
Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)
> there is a good reason to do so. Especially considering that using
> mpfr's functions was abotu a million times faster since there is no
> pexpect overhead. I could see using that code in case the argument is
> non-integer, but not using the highly optimized gmp implementation for
> something that is many orders of magnitude slower is just not what we
> want to do.
If a ticket is posted with the third patch, the reviewer should just make
sure that factorial(n) for input an integer (1) doesn't slow down, and (2)
returns an integer.
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
mabshoff
On Nov 2, 12:07 pm, "William Stein" <wst...@gmail.com> wrote:
>
> > On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:
> >> On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss
>
> > Hi,
>
> >> <h...@finanz.math.tugraz.at> wrote:
>
> >> > Hi,
>
> >> > I have written some code for the Maxima interface.
> >> > You can find the patches at:
> >> > http://www.math.tugraz.at/~huss/sage
>
> >> > calculus1.patch implements the conversion from Maxima
> >> > matrices to Sage matrices.
>
> > This should come in handy, but starting with 3.2 we will finally have
> > pynac available for some of the basic symbolic manipulation tasks. It
> > is far from bullet proof, but it is a start, so the days of Maxima as
> > the default implementation of the low level symbolic stuff is coming
> > finally to an end :)
>
> And I think we still want to have as many conversions between
> Maxima and Sage as possible, even if Maxima isn't the default
> backend for symbolic manipulation. It's still very good for
> Maxima and Sage to be able to communicate. The more
> capabilities for communication between Sage and other systems,
> the better.
functionality directly implemented in Sage than to use Maxima for say
the generation of a Vandermonde matrix. Sooner or later someone will
complain about the performance when it is generated in Maxima since
due to pexpect it can never approach native speed implementations for
something where the overhead to computational ratio is so bad. That
obviously applies to any system that has to communicate via pexpect
for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
but computations where the communication overhead is tiny compared to
the computational effort the pexpect overhead is negligible can employ
pexpect without too much of a penalty. William and I disagree on this
point, but in 10 years I see very little non-optional functionality in
Sage provided via pexpect since someone in the Sage project will
either have implemented the functionality natively or the project we
are using has been library-fied some way.
> >> > calculus2.patch adds symbolic gamma and factorial functions.
> >> > (The factorial is named fact() so it doesn't clash with the
> >> > factorial in sage.rings.arith)
>
> > Provided the factorial bit does not interfere with the current non-
> > symbolic code this could be useful.
>
> +1
>
>
>
> >> > Finally calculus3.patch renames the symbolic factorial to factorial(),
> >> > and changes all imports of sage.rings.arith.factorial to
> >> > sage.calculus.calculus.factorial. I had to keep a renamed version
> >> > of the factorial function in sage.rings.arith to avoid circular
> >> > imports at startup.
>
> > I don't like this patch at all since it forces us to use a Maxima
> > function even for integers which ought to be the most common use of
> > factorial.
>
> I didn't look at the patch, but just want to comment that using
> sage.calculus.calculus.factorial instead of sage.rings.arith.factorial
> doesn't a priori imply that Maxima is used to compute factorials.
> I.e., I could imagine an implementation where GMP is still used
> for this:
>
> sage: time n = factorial(10^6)
> CPU times: user 1.90 s, sys: 0.10 s, total: 2.00 s
coerced into an Integer and should that fail have pynac/Maxima have a
go at it.
> > When the point counting code was using Maxima to compute
> > ceil, floor and sqrt the code as a whole was slower by a factor of
> > three which illustrates nicely why we don't want to use Maxima unless
>
> Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)
floor and sqrt from calculus. And those values were only used to
determine some thresholds for the computation and barely used any
significant time in to algorithm. But using the calculus functionality
instantly I noticed that performance went to shit, so I complained
about it and ceil, floor and sqrt in that code are no longer imported
from calculus :)
> > there is a good reason to do so. Especially considering that using
> > mpfr's functions was abotu a million times faster since there is no
> > pexpect overhead. I could see using that code in case the argument is
> > non-integer, but not using the highly optimized gmp implementation for
> > something that is many orders of magnitude slower is just not what we
> > want to do.
>
> If a ticket is posted with the third patch, the reviewer should just make
> sure that factorial(n) for input an integer (1) doesn't slow down, and (2)
> returns an integer.
Cheers,
Michael
William Stein
It's not only pexpect. It's that maxima via clisp is itself very slow.
> obviously applies to any system that has to communicate via pexpect
> for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
> but computations where the communication overhead is tiny compared to
> the computational effort the pexpect overhead is negligible can employ
> pexpect without too much of a penalty. William and I disagree on this
> point, but in 10 years I see very little non-optional functionality in
> Sage provided via pexpect since someone in the Sage project will
> either have implemented the functionality natively or the project we
> are using has been library-fied some way.
I hope I'm wrong!
Thanks for the clarification. Now I remember what you're talking about.
>> > there is a good reason to do so. Especially considering that using
>> > mpfr's functions was abotu a million times faster since there is no
>> > pexpect overhead. I could see using that code in case the argument is
>> > non-integer, but not using the highly optimized gmp implementation for
>> > something that is many orders of magnitude slower is just not what we
>> > want to do.
>>
>> If a ticket is posted with the third patch, the reviewer should just make
>> sure that factorial(n) for input an integer (1) doesn't slow down, and (2)
>> returns an integer.
>
> +1
>
> Cheers,
>
> Michael
> >
>
--
mabshoff
On Nov 2, 12:36 pm, "William Stein" <wst...@gmail.com> wrote:
> On Sun, Nov 2, 2008 at 12:24 PM, mabshoff <mabsh...@googlemail.com> wrote:
<SNIP>
> > Yes, I do not disagree, but I would much rather see fundamental
> > functionality directly implemented in Sage than to use Maxima for say
> > the generation of a Vandermonde matrix. Sooner or later someone will
> > complain about the performance when it is generated in Maxima since
> > due to pexpect it can never approach native speed implementations for
> > something where the overhead to computational ratio is so bad. That
>
> It's not only pexpect. It's that maxima via clisp is itself very slow.
with sbcl either, but there are certainly useful and some times very
complex algorithms implemented in Maxima. Way back it was the right
decision to use Maxima to get up to speed quickly, but as is many
people would claim that for limits or integration it cannot compete
with either MMA or Maple, hence the drive to do our own
implementations starting from the bottom up.
> > obviously applies to any system that has to communicate via pexpect
> > for licensing or technical reasons, i.e. GAP, Axiom, Magma and so on,
> > but computations where the communication overhead is tiny compared to
> > the computational effort the pexpect overhead is negligible can employ
> > pexpect without too much of a penalty. William and I disagree on this
> > point, but in 10 years I see very little non-optional functionality in
> > Sage provided via pexpect since someone in the Sage project will
> > either have implemented the functionality natively or the project we
> > are using has been library-fied some way.
>
> I hope I'm wrong!
inclusion in Sage doing the same thing I always would prefer the
library solution even if it means more work. pexpect in the long term
is just a crutch for something that could be linked in as a library.
<SNIP>
> >> Do you really mean "three orders of magnitude", i.e., a factor of 1000? :-)
>
> > The doctest jumped from about 250 seconds to 800 just by using ceil,
> > floor and sqrt from calculus. And those values were only used to
> > determine some thresholds for the computation and barely used any
> > significant time in to algorithm. But using the calculus functionality
> > instantly I noticed that performance went to shit, so I complained
> > about it and ceil, floor and sqrt in that code are no longer imported
> > from calculus :)
>
> Thanks for the clarification. Now I remember what you're talking about.
double precision version used previously was insufficient due to too
little precision. Right now we should be using mpfr versions of those
functions which are plenty fast and exact on all platforms :)
Cheers,
Michael
Wilfried_Huss
> Thanks! Could you write to Michael Abshoff (<mabsh...@googlemail.com>) and ask
> for each of the above? Thanks again!
Greetings,
Wilfried
Wilfried_Huss
On 2 Nov., 20:46, mabshoff <mabsh...@googlemail.com> wrote:
> On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:
>
> > On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss
>
> Hi,
>
>
>
> > <h...@finanz.math.tugraz.at> wrote:
>
> > > Hi,
>
> > > I have written some code for the Maxima interface.
> > > You can find the patches at:
> > > http://www.math.tugraz.at/~huss/sage
>
> > > calculus1.patch implements the conversion from Maxima
> > > matrices to Sage matrices.
>
> This should come in handy, but starting with 3.2 we will finally have
> pynac available for some of the basic symbolic manipulation tasks. It
> is far from bullet proof, but it is a start, so the days of Maxima as
> the default implementation of the low level symbolic stuff is coming
> finally to an end :)
level
symbolic stuff for the foreseeable future. So I think it makes sense
to have
the conversions between Sage and Maxima as complete as possible.
> > > calculus2.patch adds symbolic gamma and factorial functions.
> > > (The factorial is named fact() so it doesn't clash with the
> > > factorial in sage.rings.arith)
>
> Provided the factorial bit does not interfere with the current non-
> symbolic code this could be useful.
>
> > > Finally calculus3.patch renames the symbolic factorial to factorial(),
> > > and changes all imports of sage.rings.arith.factorial to
> > > sage.calculus.calculus.factorial. I had to keep a renamed version
> > > of the factorial function in sage.rings.arith to avoid circular
> > > imports at startup.
>
> I don't like this patch at all since it forces us to use a Maxima
> function even for integers which ought to be the most common use of
> factorial.
Just as before factorial(x) just tries to call
x.factorial()
only if this raises an exception the symbolic version is
constructed.
sage: def f(n):
sage: s = 0
sage: for i in xrange(n):
sage: s += factorial(2^i)
sage: return s.ndigits()
sage: time f(22)
12346641
CPU time: 10.89 s, Wall time: 10.94 s
This is the same with or without the patch.
Wilfried
Robert Bradshaw
> On 2 Nov., 20:46, mabshoff <mabsh...@googlemail.com> wrote:
>> On Nov 2, 11:38 am, "William Stein" <wst...@gmail.com> wrote:
>>
>>> On Sun, Nov 2, 2008 at 3:10 AM, Wilfried_Huss
>>>> I have written some code for the Maxima interface.
>>>> You can find the patches at:
>>>> http://www.math.tugraz.at/~huss/sage
>>
>>>> calculus1.patch implements the conversion from Maxima
>>>> matrices to Sage matrices.
>>
>> This should come in handy, but starting with 3.2 we will finally have
>> pynac available for some of the basic symbolic manipulation tasks. It
>> is far from bullet proof, but it is a start, so the days of Maxima as
>> the default implementation of the low level symbolic stuff is coming
>> finally to an end :)
>
> Yes, but as far as I understand Maxima will still be used for the high
> level
> symbolic stuff for the foreseeable future. So I think it makes sense
> to have
> the conversions between Sage and Maxima as complete as possible.
Yes, and even when it's not called in the background for a lot of
stuff, it will be very useful to have good conversion routines. For
example, right now there is a lot of hard work going on to improve
the sage-magma interface despite the fact that magma is an optional
package.
That sounds very good. Did you make a ticket?
- Robert
Wilfried_Huss
On 2 Nov., 12:10, Wilfried_Huss <h...@finanz.math.tugraz.at> wrote:
> Hi,
>
> I have written some code for the Maxima interface.
> You can find the patches at:
> http://www.math.tugraz.at/~huss/sage
>
> calculus1.patch implements the conversion from Maxima
> matrices to Sage matrices.
> calculus2.patch adds symbolic gamma and factorial functions.
> (The factorial is named fact() so it doesn't clash with the
> factorial in sage.rings.arith)
> Finally calculus3.patch renames the symbolic factorial to factorial(),
> and changes all imports of sage.rings.arith.factorial to
> sage.calculus.calculus.factorial. I had to keep a renamed version
> of the factorial function in sage.rings.arith to avoid circular
> imports at startup.