Yeah, the divisors function otherwise kicks proverbial:
Here in Sage (excuse my rubbish python):
def random(n):
a = ZZ.random_element(n)
return a
def z_divisors_test(m):
for j in range(0, m) :
n = random(10)
z = 1
c = 1
for i in range(0, n):
k = random(100).next_prime()
if gcd(k, z) == 1 :
e = random(8)
c = c*(e+1)
z = z*(k^e)
l = z.divisors()
if len(l) != c:
print "Error", len(l), "!=", c, "for integer", z
time z_divisors_test(2000)
Something like 40s.
Here in Magma (excuse my even more rubbish Magma coding skills):
t:= Cputime();
for j := 0 to 2000 do
n := Random(10);
z:=1;
c:=1;
for i := 0 to n do
k := NextPrime(Random(100));
if Gcd(k,z) eq 1 then
e := Random(8);
c := c*(e+1);
z := z*(k^e);
end if;
end for;
l := Divisors(z);
if #l ne c then
print "Error";
end if;
end for;
Cputime(t);
Umm, yeah. Not worth waiting up for. :-)
Magma does use half the memory though.
Bill.
On 8 Apr, 06:44, Robert Bradshaw <rober...@math.washington.edu> wrote:
> On Apr 7, 2009, at 10:26 PM, Bill Hart wrote:
>
>
>
> > William didn't mention the context of this, which is that for small
> > integers most of the time taken by the divisors method in ZZ is taken
> > up with factoring. It seems much more likely people will use small
> > numbers as inputs to this, so this is a shame, given the amount of
> > work that (I hear) went into optimising that in Sage.
>
> > Bill.
>
> Hmm.. that's not always true, at least the cases that inspired this
> ticket:
>
> sage: n = ZZ(odd_part(factorial(31)))
> sage: timeit('n.factor()')
> 625 loops, best of 3: 294 µs per loop
> sage: timeit('n.divisors()')
> 5 loops, best of 3: 104 ms per loop
>
> So for some highly composite numbers, factoring is the minority of
> the time. (BTW, before the optimization, this took nearly 2.5
> seconds!) Of course usually for numbers of this size there are only a
> few factors, so the divisors function is dominated by the much harder
> problem of factoring (which can clearly use some fixing).
>
> - Robert
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
