William didn't mention the context of this, which is that for small
integers most of the time taken by the divisors method in ZZ is taken
up with factoring. It seems much more likely people will use small
numbers as inputs to this, so this is a shame, given the amount of
work that (I hear) went into optimising that in Sage.
Bill.
On 8 Apr, 06:18, Bill Hart <goodwillh...@googlemail.com> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
