Daryl Hammond wrote:
> 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')
The above seems to take about 14s
Why not just do:
p = ['1']*n or p=['1']*(n+1) (depending on how your indices work out, I
think it's n+1).
which takes about 164 ms?
>
> 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
The above takes about 16s
Why not use:
ctr = p.count('1')
which takes about 363ms?
>
> 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
The original program gives (on my computer):
============================================
SAGE Version 3.0.1, Release Date: 2008-05-05
Start time: Thu Jul 3 06:22:07 2008
Array size: 10000000
Create array: Thu Jul 3 06:22:31 2008
Create seconds: 24.6
Mark primes: Thu Jul 3 06:23:13 2008
Mark seconds: 42.16
Count primes: Thu Jul 3 06:23:33 2008
Count seconds: 19.14
Number of primes: 664579
End time: Thu Jul 3 06:23:33 2008
Elapsed seconds: 85.9
============================================
To compare, with the above modifications:
============================================
SAGE Version 3.0.1, Release Date: 2008-05-05
Start time: Thu Jul 3 05:46:28 2008
Array size: 10000000
Create array: Thu Jul 3 05:46:28 2008
Create seconds: 0.32
Mark primes: Thu Jul 3 05:47:15 2008
Mark seconds: 46.48
Count primes: Thu Jul 3 05:47:15 2008
Count seconds: 0.3
Number of primes: 664579
End time: Thu Jul 3 05:47:15 2008
Elapsed seconds: 47.1
============================================
In addition, if you want to use python ints instead of sage Integers,
replace:
n = 10*1000*1000 with
n = int(10 * 1000 * 1000)
and
q = 1 with
q = 1r
and
q = q + 1 with
q = q + 1r
With this change, I get:
============================================
SAGE Version 3.0.1, Release Date: 2008-05-05
Start time: Thu Jul 3 05:51:05 2008
Array size: 10000000
Create array: Thu Jul 3 05:51:06 2008
Create seconds: 0.57
Mark primes: Thu Jul 3 05:51:33 2008
Mark seconds: 27.6
Count primes: Thu Jul 3 05:51:34 2008
Count seconds: 0.46
Number of primes: 664579
End time: Thu Jul 3 05:51:34 2008
Elapsed seconds: 28.62
============================================
This is definitely comparable to the "interpreted" maple timing since it
uses python lists instead of hardware data arrays.
Switching to cython gives makes the program run in about 0.7s (so pretty
much the same as the Maple program). The Cython code is:
%cython
cpdef int sieve(int n):
cdef char *p = <char *> sage_malloc((n+1) * sizeof(char))
cdef int i = 0
for i from 0<= i < (n+1):
p[i] = '1'
#-----------------------------------------------
# initialize first two array elements to '0'
p[0] = '0'
p[1] = '0'
# assign '0' to non-prime numbers
cdef int q = 1
cdef int z = 0
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'
#-----------------------------------------------
# count primes and print count
cdef int ctr = 0
i = 0
for i from 0<= i < (n+1):
if p[i] == '1':
ctr += 1
return ctr
Thanks,
Jason
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
