Re: adding Proof option to factor()

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* Bill Allombert [2007-09-18 01:45]:
> On Wed, Sep 12, 2007 at 12:35:03PM +0200, Karim Belabas wrote:
> > * John Cremona [2007-09-07 11:18]:
> > > The factor() function for integers (i.e. factorint()) does not provide
> > > factors which are proved to be prime, unless they are are < 10^15,
> > > accoriding to the manual.  The manual recommends using isprime() in
> > > circumstances where proven primes are required.
> > > 
> > > Could we add another flag to the function which defaults to 0 but if
> > > set does the proving step too?  I use pari's factor() in mwrank and am
> > > not happy that I cannot guarantee results because of this, and it
> > > would be a lot easier to just add af lag to the call I make to
> > > factor().
> > 
> > I don't like complicating the user interface for something which is easy to
> > implement externally, usually in a more flexible way. There's already an
> > optional argument to factor, and having two flags is very error-prone
> > [ consider factor(n,1), factor(n,,1), factor(n,100000,1),
> > factor(n,1,10000), etc. ]
> 
> Please note that we have factorint which already accept a flag.

OK, the above comment doesn't apply to factorint. I have nothing against
adding a new significant bit to the existing flag. But I like your other
suggestion better:

> But actually what we need is a default(), not a flag: factorisation is a
> pervasive operation in PARI/GP, and if you want a proven result, you
> have to prove each and every factorizations that occurs during the
> computation. 

Not quite true: e.g. nfdisc & friends are often quite happy (and *much* faster)
with partial factorizations of the discriminant, in turn contaminating
most of the algebraic number theory routines. Of course, in that case the
caller explicitly asked for partial factorization, so the default shouldn't
apply.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

OK, Done in CVS.

Minor slowdown in most cases:

(10:50) gp > default(factor_proven,1);
(10:50) gp > factor(2^2^7+1);
time = 301 ms.
(10:50) gp > default(factor_proven,0);
(10:50) gp > factor(2^2^7+1);
time = 295 ms.

Major slowdown in fringe cases (e.g. huge pure powers, up to small factors):

(10:51) gp > N = nextprime(10^500)^2;
(10:51) gp > default(factor_proven,0); factor(N);
time = 559 ms.
(10:51) gp > default(factor_proven,1); factor(N);
time = 5mn, 47,049 ms.

Cheers,

    K.B.

P.S: About adding flags. We already have an infrastructure for symbolic flags
(cf ??ploth and the beginning of Chapter 3 in User's Guide) but I do not
quite know what to make of it: as long as explicit numerical values
coexist with the symbolic names, we may not internally change the
meaning / reorder of specific bits; and in interactive use, purely
symbolic flags are cumbersome, hence annoying...

Currently, the only real use of symbolic lags would be to write cleaner-looking
scripts, easier to maintain. (But then, many more functions should be
equipped with them, instead of our single 'ploth' prototype.)

P.S2: Hum, symbolic flags seem to be broken in current CVS:

  ploth(t=0,Pi,[sin(t),cos(t)], Parametric)

no longer works:

  ***   gtos expected an integer, got 'Parametric'.

-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]