Thanks Alec for pointing out the incorrect prime count (I was failing
to mark the
last element in the array as non-prime).
Michael, I divided the sieve program into three parts: create array,
mark primes, and
count primes. I then ran the sieve program under sage-3.0.1 and
sage-3.0.2.
Here is a summary of the times in seconds and percent:
(seconds) 3.0.1 3.0.2 (percent) 3.0.1 3.0.2
Create array 15.84 25.71 Create array 22 21
Mark primes 38.08 69.22 Mark primes 53 56
Count primes 17.62 28.96 Count primes 25 23
------------------------------------------------------------------
Elapsed 71.55 123.89 Elapsed 100 100
It looks like the GMP regression is effecting all parts of the program
equally.
When looked at from a percentage basis, there isn't much difference
in
percentages among the three parts of the program when run under
Sage-3.0.1 or
Sage-3.0.2.
Detailed timings and a revised sieve program follow:
/home/daryl/sage-3.0.1/sage /home/daryl/UserData/sage/sieve.sage
============================================
SAGE Version 3.0.1, Release Date: 2008-05-05
Start time: Thu Jul 3 00:31:35 2008
Array size: 10000000
Create array: Thu Jul 3 00:31:51 2008
Create seconds: 15.84
Mark primes: Thu Jul 3 00:32:29 2008
Mark seconds: 38.08
Count primes: Thu Jul 3 00:32:46 2008
Count seconds: 17.62
Number of primes: 664579
End time: Thu Jul 3 00:32:46 2008
Elapsed seconds: 71.55
============================================
/home/daryl/sage-3.0.2/sage /home/daryl/UserData/sage/sieve.sage
============================================
SAGE Version 3.0.2, Release Date: 2008-05-24
Start time: Thu Jul 3 00:32:49 2008
Array size: 10000000
Create array: Thu Jul 3 00:33:15 2008
Create seconds: 25.71
Mark primes: Thu Jul 3 00:34:24 2008
Mark seconds: 69.22
Count primes: Thu Jul 3 00:34:53 2008
Count seconds: 28.96
Number of primes: 664579
End time: Thu Jul 3 00:34:53 2008
Elapsed seconds: 123.89
============================================
cat /home/daryl/UserData/sage/sieve.sage
#!/usr/bin/env sage
# sieve of Erasthenes
# 2008/07/02 DWH Fix bug not processing last element in array
# 2008/04/29 DWH Switch from numerical array to character array for
primes;
# Switch from srange() to while loop.
#
#-------------------------------------------------------------------------------
from time import *
# print start time
print
print '============================================'
print version()
print
start = time()
print 'Start time: ', ctime(start)
print
#create prime array p of size n and initialize to '1'
n = 10 * 1000 * 1000
print 'Array size: ', n
p = list()
array_ctr = -1
while array_ctr < n:
array_ctr = array_ctr + 1
p.append('1')
create = time()
print
print 'Create array: ', ctime(create)
elapsed = create - start
print 'Create seconds: ', round(elapsed,2)
#-----------------------------------------------
# initialize first two array elements to '0'
p[0] = '0'
p[1] = '0'
# assign '0' to non-prime numbers
q = 1
while q * q < n:
q = q + 1
if p[q] == '1':
z = q * q - q
while z + q <= n:
z = z + q
p[z] = '0'
mark = time()
print
print 'Mark primes: ', ctime(mark)
elapsed = mark - create
print 'Mark seconds: ', round(elapsed,2)
#-----------------------------------------------
# count primes and print count
ctr = 0
array_ctr = -1
while array_ctr < n:
array_ctr = array_ctr + 1
if p[array_ctr] == '1':
ctr = ctr + 1
count = time()
print
print 'Count primes: ', ctime(count)
elapsed = count - mark
print 'Count seconds: ', round(elapsed,2)
print
print 'Number of primes:', ctr
# print end time
print
end = time()
print 'End time: ', ctime(end)
elapsed = end - start
print 'Elapsed seconds: ', round(elapsed,2)
print
print '============================================'
print
--~--~---------~--~----~------------~-------~--~----~
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
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
