Hi,
What the status is of factoring integers: from 1 up to 80-100 digits?
Ticket #5310 seems to address this by implementing Msieve, but I
noticed no activity lately.
For instance n.trail_division() speeds up calculations a lot, but it
seems not be integrated with a general approach. This implies that for
small integers up to 10^8 the speed of n.trail_division() seems not to
be used by factor().
To illustrate my point, please look at the following example.
def fastfactor(n):
if n in [1,0,-1]: return [(n,1)]
uit=[]
d=1
while n not in [1,d]:
d=n.trial_division()
e=1
n=n//d
while n%d==0:
e+=1
n=n//d
uit.append((d,e))
if n>1: uit.append((n,1))
return uit
m=6
timeit('for i in xsrange(10^m,10^m+1000): fastfactor(i)')
timeit('for i in xsrange(10^m,10^m+1000): list(i.factor())')
25 loops, best of 3: 8.15 ms per loop
25 loops, best of 3: 30.6 ms per loop
I sincerely hope that release 4.7.3 will also focus on speeding up the
most used functions like factor, but also uniq, gcd, xgcd and other
elementary functions.
Thanks in advance for your informative reply.
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
