Not an issue - Python with Numba, faster than C#

[cristi-neagu]

Hello,

This is not really an issue. Wanted to share a version of the Python code using Numba. But because this is the first time i used Numba and i don't really know how to use jitclass, i had to pull the code apart so it's pretty ugly. As such, i didn't want to submit it as a pull request. Hopefully someone can make a prettier version.

On my machine this ran faster than the C# version, with 4855 iterations vs 4150.

from sys import stdout
from math import sqrt                       # Used by the sieve
import timeit                               # For timing the durations
import numpy as np
from numba import njit

@njit
def primeSieve(limit=1000000):
    rawbits = np.full(int((limit+1)/2), np.bool(True))

    factor = 3
    q = sqrt(limit)
    num = 0

    while factor < q:
        for num in range (factor, limit):
            if num % 2 == 0:
                continue

            if rawbits[int(num/2)]:
                factor = num
                break

        # If marking factor 3, you wouldn't mark 6 (it's a mult of 2) so start with the 3rd instance of this factor's multiple.
        # We can then step by factor * 2 because every second one is going to be even by definition

        for num in range (factor * 3, limit, factor * 2):
            if num % 2 == 0:
                continue
            rawbits[int(num/2)] = False

        factor += 2 # No need to check evens, so skip to next odd (factor = 3, 5, 7, 9...)
    return rawbits

def printResults(showResults, rawbits, duration, passes, sieveSize):
    if showResults: # Since we auto-filter evens, we have to special case the number 2 which is prime
        stdout.write("2, ")

    count = 1
    for num in range (3, sieveSize): # Count (and optionally dump) the primes that were found below the limit
        if num % 2 == 0:
            continue
        if rawbits[int(num/2)]:
            if showResults:
                stdout.write(str(num) +", ")
            count+=1

    countPrimes = sum(1 for b in rawbits if b)
    assert count == countPrimes
    stdout.write("\n")

    primeCounts = { 10 : 1,                 # Historical data for validating our results - the number of primes
                    100 : 25,               # to be found under some limit, such as 168 primes under 1000
                    1000 : 168,
                    10000 : 1229,
                    100000 : 9592,
                    1000000 : 78498,
                    10000000 : 664579,
                    100000000 : 5761455
                  }

    if sieveSize in primeCounts:      # the data, and (b) our count matches. Since it will return
        validateResults = (primeCounts[sieveSize] == countPrimes)
    else:
        validateResults = False

    print("Passes: " + str(passes) + ", Time: " + str(duration) + ", Avg: " + str(duration/passes) +
          ", Limit: " + str(sieveSize) + ", Count: " + str(count) + ", Valid: " + str(validateResults))

tStart = timeit.default_timer()                         # Record our starting time
totPass = 0
numSieve = 1000000
while timeit.default_timer() - tStart < 10:           # Run until more than 10 seconds have elapsed
    res = primeSieve(numSieve)                        #  Calc the primes up to a million
    totPass = totPass + 1                                 #  Count this pass

tD = timeit.default_timer() - tStart

printResults(False, res, tD, totPass, numSieve)

[LanceMcCarthy]

You should open a Pull Request instead of Issue, that way other devs can include/test/compare yours. https://github.com/davepl/Primes/pulls

[cristi-neagu]

@LanceMcCarthy Like i said, i mangled the code quite a bit, so i don't think it's fit for a PR. It's here for review, maybe it encourages someone more proficient with Numba to have a go.

[cristi-neagu]

Actually, i see @rhbvkleef submitted #9 that closes this. As expected, he did a lot better than me, with it running about twice as fast than my naive implementation.