On 30 Okt., 23:29, William Stein <[email protected]> wrote: > On Sun, Oct 30, 2011 at 1:00 PM, Rolandb <[email protected]> wrote: > > > On 30 okt, 03:13, William Stein <[email protected]> wrote: > >> Sage's factor currently just calls pari which makes no use of anything > >> anywhere else in sage. It would be nice if somebody were to change this, > >> but I have seen many people try and fail. > > > Dear William, > > > I'm still puzzled why I find such a difference in performance. Looking > > at the listing of n.factor, factor_trial_division is used if n<2^40. > > if mpz_sizeinbase(n.value, 2) < 40: > > from sage.rings.factorint import factor_trial_division > > return factor_trial_division(self) > > > So I would expect a similar timeit result for the first and last > > example. It almost seems that there is a some overhead in factoring > > small integers. I found that Sebastian Pancratz also indicated the > > performance drag late 2010. > > For instance with n.factor(): > > > from sage.structure.factorization import Factorization > > from sage.structure.factorization_integer import > > IntegerFactorization > > > are called each time which are not always relevant. > > > Maybe the order could be changed somewhat. For instance: > > if n integer or int: > > - n==0 -> error message > > - n in [1,-1] -> 1,-1 > > - n < 2^40: factor_trail_division > > And all other cases thereafter. > > Great idea. Can you make a trac ticket and submit a patch, please?
trial_division() should also take an (optional) *lower* bound on the divisor, which could speed up things significantly if you call it repeatedly. It could also (optionally) use PARI's prime table instead of a modulo-30 wheel. -leif -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
