1
\$\begingroup\$

I decided to write a sieving prime-finding programme and make it fast. It works correctly but counting the primes below 10**9 takes 36 times as primesieve downloaded from http://primesieve.org/.

Now I understand that they have a World Record so they better be fast, but we all know that a compiler is much better than a human at making optimization, so I fear I missed a massive optimization in my implementation.

Some timings:

time ./sieve-c 100000000
Up to 100000000 there are 5761455 primes.

real  0m1.914s
user  0m1.876s
sys   0m0.032s


time ./primesieve 100000000
Sieve size = 32 kilobytes
Threads    = 4
100%
Prime numbers : 5761455
Time elapsed  : 0.0568619 sec

real  0m0.206s
user  0m0.192s
sys   0m0.004s

time ./sieve-c 1000000000
Up to 1000000000 there are 50847534 primes.

real  0m21.408s
user  0m21.128s
sys   0m0.252s


time ./primesieve 1000000000
Sieve size = 32 kilobytes
Threads    = 4
100%
Prime numbers : 50847534
Time elapsed  : 0.582213 sec

real  0m0.607s
user  0m2.220s
sys   0m0.000s

Where should I go next for better performance (wheel factorization, memoization, segmentation, parallelism)?

Also, my code is not able to calculate 10**10 or more because that would take up too much space and my computer crashes. Maybe I should try segmentation?

Please note that R-Python is a subset of Python, so you can run my programme with a regular Python too (but it will be much slower).

import doctest
import math
import sys
import doctest

def sieve(limit):
    """
    Returns the primes below the `limit`

    >>> sieve(9)
    [False, False, True, True, False, True, False, True, False]
    >>> sieve(100000).count(True)
    9592
    """
    sieve = [True]*limit
    sieve[0],sieve[1] = False, False
    sqrt_limit = math.sqrt(limit)
    for number, prime in enumerate(sieve):
        if prime:
            for multiple in xrange(number*2, limit, number):
                sieve[multiple] = False
        if number > sqrt_limit:
            break
    return sieve

doctest.testmod()

def _sum(lst):
    s = 0
    for i in lst:
        s += i
    return s

def main(argv):
    print("Up to " + argv[1] +" there are " +str(_sum(sieve(int(argv[1])+1))) + " primes.")
    return 0

def target(*args):  
    return main, None

if __name__ == '__main__':  
    import sys
    main(sys.argv)
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Did you read the documentation on primesieve.org? They use several key optimizations to the Sieve of Erastothenes, most notably it's segmented and they use wheel factorization. Your code doesn't do either of those. \$\endgroup\$
    – Snowbody
    May 4, 2015 at 14:25
  • \$\begingroup\$ RPython is a really strange target for this IMHO. I'm also not enthused about the "my implementation is slower than another with more optimizations - why?" aspect of the question. I might look at this a bit, but language unfamiliarity will probably prevent any really good answers. \$\endgroup\$
    – Veedrac
    May 4, 2015 at 14:47
  • \$\begingroup\$ Please remember to use python as well. That may be a reason why this question hasn't been answered. \$\endgroup\$
    – Jamal
    Feb 11, 2016 at 19:31
  • 1
    \$\begingroup\$ How would Python code be slower in Python than in RPython? R is slower than Python, and I assume any code ran native will be faster. Very curious. \$\endgroup\$ May 6, 2016 at 16:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.