[julia-users] Sieve of Atkin performance.

[Ismael VC]

Hello everyone!

I’ve implemented this Sieve of Atkin: 

   - https://gist.github.com/Ismael-VC/179790a53c549609b3ce 

function atkin(limit::Int = 0)
    @inbounds begin
        primes = [2, 3]

        if limit < 0
            error("limit can't be negative (found $(limit))")

        elseif limit < 2
            primes = Int[]

        elseif limit == 2
            primes = [2]

        else
            factor = round(Int, sqrt(limit))
            sieve = falses(limit)

            for x = 1:factor
                for y = 1:factor
                    n = 4x^2 + y^2
                    if n <= limit && (n % 12 == 1 || n % 12 == 5)
                        sieve[n] = !sieve[n]
                    end

                    n = 3x^2 + y^2
                    if n <= limit && n % 12 == 7
                        sieve[n] = !sieve[n]
                    end

                    n = 3x^2 - y^2
                    if x > y && n <= limit && n % 12 == 11
                        sieve[n] = !sieve[n]
                    end
                end
            end

            for x = 5:factor
                if sieve[x]
                    for y = x^2 : x^2 : limit
                        sieve[y] = false
                    end
                end
            end

            for i = 5:limit
                if sieve[i]
                    push!(primes, i)
                end
            end
        end
    end
    return primes
end

Ported directly from the Wikipedia pseudocode:

   - https://en.wikipedia.org/wiki/Sieve_of_Atkin#Pseudocode 

And I’ve also compared atkin with Base.primes (IJulia notebook tested at 
JuliaBox version 0.4.0-dev+5491):

   - http://nbviewer.ipython.org/gist/Ismael-VC/25b1a0c1e11f306a40ae 

I also tested it on a Mac:

ulia> versioninfo()
Julia Version 0.3.9
Commit 31efe69 (2015-05-30 11:24 UTC)
Platform Info:
System: Darwin (x86_64-apple-darwin13.4.0)
CPU: Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
WORD_SIZE: 64
BLAS: libopenblas (USE64BITINT DYNAMIC_ARCH NO_AFFINITY Sandybridge)
LAPACK: libopenblas
LIBM: libopenlibm
LLVM: libLLVM-3.3

julia> gc(); @time primes(1000_000_000);
elapsed time: 72.423236327 seconds (531889264 bytes allocated, 0.02% gc time)

julia> gc(); @time atkin(1000_000_000);
elapsed time: 27.908726228 seconds (2342278320 bytes allocated, 0.17% gc time)

julia> gc(); @time primes(10_000_000_000);
elapsed time: 809.601231674 seconds (4890727200 bytes allocated, 0.00% gc time)

julia> gc(); @time atkin(10_000_000_000);
elapsed time: 332.286719798 seconds (160351721104 bytes allocated, 0.32% gc 
time)

Reference: 

   - https://github.com/JuliaLang/julia/issues/11594#issuecomment-115915833 

I’m trying to understand how does Base.primes and the Base.primesmask 
functions work and also how is it that atkin performs better in time (and 
sometimes also in space) than Base.primes in this tests.
​