Then again, if one works in a number field in Magma instead of a
quotient ring, it takes about a quarter of the time of SAGE to do the
power. That's probably about comparable to what we'd get with a single
scaling before and after doing the powering in SAGE. So it looks like
when all the appropriate improvements are in place, SAGE is going to
totally rock at this matrix powering benchmark.
Bill.
On 3 Dec, 22:10, Bill Hart <[EMAIL PROTECTED]> wrote:
> Magma also takes 0.12s to do the polynomial expmod a^20000 mod f, but
> when you raise the power to 200000 or 2000000 Magma is not competitive
> any more. This is quite surprising, since as everyone knows, Magma is
> usually quite competitive with polynomial arithmetic.
>
> Bill.
>
> On 3 Dec, 18:26, Bill Hart <[EMAIL PROTECTED]> wrote:
>
> > On 3 Dec, 16:16, "William Stein" <[EMAIL PROTECTED]> wrote:
>
> > > By the way, PARI is *not* competitive here:
>
> > > sage: nn = gp(n)
> > > sage: gp.eval('gettime; a = %s^20000; gettime/1000.0'%nn.name())
> > > '0.42800000000000000000000000000000000000'
> > > sage: gp.eval('gettime; a = %s^200000; gettime/1000.0'%nn.name())
> > > '14.084000000000000000000000000000000000'
>
> > When you use polmods in Pari, it is actually faster than SAGE:
>
> > ? f=x^3 + 37/10*x^2 - 8/15*x + 1/60
> > ? a=Mod(x,f)
> > ? #
> > ? a^20000;
> > time = 120 ms.
> > ? a^200000;
> > time = 3,865 ms.
>
> > For a^2000000 Pari chokes and takes about 3 times longer than SAGE.
> > But the algorithm it uses is not optimal for such things.
>
> > I think scaling, doing the arithmetic, then scaling back sounds like a
> > good option. Does SAGE really do the computation without doing that in
> > the first place?
>
> > Bill.
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
