On Apr 9, 2:03 pm, Peter Jeremy <peterjer...@optushome.com.au> wrote:
> On 2009-Apr-07 21:49:12 -0700, William Stein <wst...@gmail.com> wrote:
>
>
>
> >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.]
>
> How often is pari's factor wrong and how? If pari's factor is
> mostly correct bu occasionally reports incorrect factors, given
> the massive discrepancy in speed, if it worthwhile always trying
> pari's fator first and then verifying its output. If it's wrong,
> then try Sage's factor.
The primality test for pari is known to be lead to false results up to
10^14 or so (FLINT's is up to 10^16 IIRC what Bill told me a couple
days ago). So for "small" integers below the bound there is no need to
verify anything.
The speed issues are with Sage calling factor() in Pari as a library,
so maybe Bill did not turn on the verify when he used Pari directly.
Either way, given the bound mentioned above where we know that Pari's
primality test without proof is correct we might want to take
advantage of that.
> The only issue I can see would be if pari sometimes incorrectly
> reports composite numbers as prime - which means every "prime" number
> reported by pari would need to be fed to Sage.
>
> --
> Peter Jeremy
Cheers,
Michael
> application_pgp-signature_part
> < 1KViewDownload
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
