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

[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.
> 
>

[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.

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

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

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
?

On Sun, Jun 28, 2015 at 11:19 AM, Ismael VC  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



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.

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

[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.

6 matches

Site Navigation

Mail list logo

Footer information