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.
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
