Proof won't make a difference on the numbers I'm using, which are less
than 1,000,000. Pari does the same thing for proving primality below
about 10^13 or something like that, whether proved or not (the
pseudoprimality test it uses is known to have no counterexample). By
the way, the FLINT function z_factor does the same thing, but for
numbers up to 10^16. Hmm, I think z_factor in FLINT is possibly faster
than Pari, though I have never timed it for integers bigger than 10^16
with proved=1 in FLINT. That might be slower, due to the primality
proving. I don't know what Pari does for that.
Bill.
2009/4/8 William Stein <wst...@gmail.com>:
> On Tue, Apr 7, 2009 at 9:24 PM, Bill Hart <goodwillh...@googlemail.com> wrote:
>> The reason it runs slow is a.factor() is bizarrely slow in Sage. It's
>> like a factor of 50 times slower than Pari.
>
> There are some differences:
> (1) pari's factor is *not* provably correct, but Sage's is. [That
> said, this will make no difference for small input.]
> (2) there is overhead in converting back and forth between data structures.
>
> What number are you factoring? I get a factor of 20 on small numbers
> and little difference on bigger ones, though again note the proof
> issue:
>
> sage: a = 10^6; timeit('factor(a)')
> 625 loops, best of 3: 156 µs per loop
> sage: a = pari(10^6); timeit('a.factor()')
> 625 loops, best of 3: 7.59 µs per loop
> sage: 156/7.59
> 20.5533596837945
> sage: a = 10^9+1; timeit('factor(a)')
> 625 loops, best of 3: 187 µs per loop
> sage: a = pari(10^9+1); timeit('a.factor()')
> 625 loops, best of 3: 11.3 µs per loop
> sage: 187/11.3
> 16.5486725663717
> sage: a = 10^30+1; timeit('a.factor()')
> 125 loops, best of 3: 1.6 ms per loop
> sage: a = pari(10^30+1); timeit('a.factor()')
> 625 loops, best of 3: 1.39 ms per loop
>
> As far as I know, nobody has spent a second in Sage seriously trying
> to optimize a.factor() for a some small integer. It would be nice if
> somebody would. This is similar to how I optimized small integer and
> rational linear algebra recently, which resulted in huge speedups in
> that.
>
> -- William
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
