Karim Belabas on Tue, 18 Sep 2007 11:13:54 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: adding Proof option to factor() |
* 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]