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? > To quicken my own calculations, I use: > > %cython > > from sage.rings.integer cimport Integer > > cpdef factor_trial_division_test(m, long limit=10**4): > > cdef Integer n = PY_NEW(Integer), unit = PY_NEW(Integer), p > cdef unsigned long e, limit2=limit*limit > cdef int i > > n = Integer(m) > if mpz_sgn(n.value) > 0: > mpz_set_si(unit.value, 1) > else: > mpz_neg(n.value,n.value) > mpz_set_si(unit.value, -1) > > F = [] > while mpz_cmpabs_ui(n.value, 1): > p = n.trial_division(bound=limit) > e = mpz_remove(n.value, n.value, p.value) > F.append((p,int(e))) > > if p>limit2: > F=F[:-1] > rest=pari(p).factor() > for i in xrange(len(rest[0])): F.append((Integer(rest[0] > [i]),int(rest[1][i]))) > > return F > > For integers up to 10^8 the speed increases threefold. So even using > Pari, it seems that factor can be made faster for smaller integers, > but I'm not knowledgeable enough to oversee the total impact of > adjusting factor. > > Roland > > -- > 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 > -- William Stein Professor of Mathematics University of Washington http://wstein.org -- 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
