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/
-~----------~----~----~----~------~----~------~--~---
