[I'm turning this into a new thread. It concerns integrating Dan
Bernstein's 'primegen' library into sage, and is ticket #3925.]
On Sun, Jul 26, 2009 at 10:56:44AM +0100, John Cremona wrote:
> As wjp says on the ticket, to try it out you only need to install the
> new spkg and the second patch. But to adopt this spkg as part of Sage
> proper would need a vote here. I suggest that wjp helps that process
> by collecting some data (before and after). For example:
>
> sage: time P = prime_range(10^8)
> CPU times: user 1.83 s, sys: 0.50 s, total: 2.32 s
> Wall time: 2.33 s
> sage: len(P)
> 5761455
>
> but this does not use the new PrimeGen class. I tried this (withe the
> new spkg + patch):
>
> sage: pg=Primes().pg
> sage: pg.reset()
> sage: N=pg.count(10^8)
> sage: pg.reset()
> sage: time P=[pg.next() for _ in range(N)]
> CPU times: user 4.98 s, sys: 0.03 s, total: 5.01 s
> Wall time: 5.02 s
The typical situation in which sage.libs.primegen.PrimeGen / Primes()
would be used is probably when you want to loop over a larger range than
can be stored in memory. I timed the following function:
def f():
P = Primes()
for p in P:
if p > 10^8:
break
# do something with p
For 10^8, this used to take 84.17s, and now takes 20.77s.
For 10^9, the runtime improved from 813.27s to 162.70s.
For 10^10, the new time is 1491.73, and the old one took too long. :-)
All these tests have the same constant low memory usage.
I ran them on a 2GHz opteron, on which the code John Cremona gives above
takes 7.21s, for comparison.
This is still about a factor 70 slower than iterating over those primes
would be in C code using Dan Bernstein's primegen, so there's probably
still room for improvement in the iterator code. (As also shown by
John's timings.)
-Willem Jan
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
