subject:"\[julia\-users\] Re\: Sieve of Atkin performance."

[julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Ismael VC

Stefan It's done, I've updated it with a MIT licence header: 
https://gist.github.com/Ismael-VC/179790a53c549609b3ce 

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.

[julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Ismael VC

I used the wikipedia spanish version and algorithm, I didn't notice that 
it's a different one in the english version:

* https://es.wikipedia.org/wiki/Criba_de_Atkin#Pseudoc.C3.B3digo

I'll check that one too.

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.

Re: [julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Stefan Karpinski

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 ismael.vc1...@gmail.com 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 (10 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.

[julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Ismael VC

Yes certainly Stefan, I'll update the gist with a MIT licence note.

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.

[julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Ismael VC



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 (10 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.

[julia-users] Re: Sieve of Atkin performance.

2015-06-28 Thread Ismael VC



Is that header ok? What do you think about this? The wikipedia article 
claims that there is room for more improvement:

This pseudocode is written for clarity; although some redundant 
computations have been eliminated by controlling the odd/even x/y 
combinations, it still wastes almost half of its quadratic computations on 
non-productive loops that don’t pass the modulo tests such that it will not 
be faster than an equivalent wheel factorized (2/3/5) sieve of 
Eratosthenes. To improve its efficiency, a method must be devised to 
minimize or eliminate these non-productive computations.

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.

[julia-users] Re: Sieve of Atkin performance.

[julia-users] Re: Sieve of Atkin performance.

Re: [julia-users] Re: Sieve of Atkin performance.

[julia-users] Re: Sieve of Atkin performance.

[julia-users] Re: Sieve of Atkin performance.

[julia-users] Re: Sieve of Atkin performance.

6 matches

Site Navigation

Mail list logo

Footer information