I mean half the memory that Sage uses, not half the memory of the
machine.
Bill.
On 8 Apr, 09:21, Bill Hart <goodwillh...@googlemail.com> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
