Are you willing to release this code under the MIT license <http://julialang.org/license>?
On Sun, Jun 28, 2015 at 11:19 AM, Ismael VC <[email protected]> wrote: > Best out of 10 runs with a limit of 100,000,000. > > - Base.primes: > > 3.514 seconds (9042 k allocations: 194 MB, 0.22% gc time) > > - atkin: > > 2.036 seconds (20 allocations: 78768 KB, 0.03% gc time) > > - eratosthenes: > > 7.272 seconds (100000 k allocations: 1677 MB, 1.58% gc time) > > El domingo, 28 de junio de 2015, 10:16:16 (UTC-5), Ismael VC escribió: > > 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. >> >> > >
