# Sieve.rb sample

the sieve of Erathotenes sample (sieve.rb) in Ruby 1.9 looks like this:

max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
sieve[i] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
puts sieve.compact.join(", ")

Is Math.sqrt(max) calculated every loop?
....
m=Math.sqrt(max)
for i in 2 .. m
....

runs about 20% faster on my machine.

···

--
Posted via http://www.ruby-forum.com/.

Hi Siep,

max = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. max
sieve[i] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
puts sieve.compact.join(", ")

Is Math.sqrt(max) calculated every loop?

Shouldn't be, no.

....
m=Math.sqrt(max)
for i in 2 .. m
....

runs about 20% faster on my machine.

I'm not sure how you're benchmarking it, but I'm not seeing such
behavior with the current svn HEAD. What I did notice, however, was
that the first run of my Benchmark seemed to be noticably quicker than
the others, which I found rather odd:

user system total real
sieve1 1.080000 0.000000 1.080000 ( 1.082122)
sieve2 1.340000 0.010000 1.350000 ( 1.350781)
sieve1 1.360000 0.000000 1.360000 ( 1.362670)
sieve2 1.350000 0.010000 1.360000 ( 1.350056)

It was even more pronounced when I upped the iterations tenfold:

user system total real
sieve1 22.510000 0.050000 22.560000 ( 22.546830)
sieve2 50.500000 0.060000 50.560000 ( 50.510556)
sieve1 50.470000 0.070000 50.540000 ( 50.500493)
sieve2 50.480000 0.080000 50.560000 ( 50.503374)

If I added a call to #sieve2 (see comment in code below) before
running the timings, the benchmarks were brought back even again:

g@bang:~/tmp\$ ruby19 sieve.rb
user system total real
sieve1 1.390000 0.000000 1.390000 ( 1.392173)
sieve2 1.370000 0.000000 1.370000 ( 1.376944)
sieve1 1.400000 0.000000 1.400000 ( 1.425670)
sieve2 1.370000 0.010000 1.380000 ( 1.393410)

Somehow calling #sieve2 is slowing down subsequent calls to #sieve1.
I don't know YARV well enough yet, but I'm curious as to what's
causing this. :-/

g@bang:~/src/ruby\$ ruby19 -v
ruby 1.9.0 (2007-11-06 patchlevel 0) [i686-linux]

Regards,
George.

Code:

def sieve1
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve[i] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

def sieve2
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve[i] = i
end

m = Math.sqrt(max)
for i in 2 .. m
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

require 'benchmark'

Benchmark.bm do |x|
# sieve2 # uncomment to remove the anomaly
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
end

···

On Nov 6, 2007 10:14 PM, Siep Korteling <s.korteling@gmail.com> wrote:

Hi team,

I executed the two versions of the program and you actually can see the
difference:
I see something estrange however. It takes less time when I execute this
program with 1000 as a parameter than when I run it with the default 100.

···

=====================================
for i in 2 .. Math.sqrt(max)

timex ruby sieve1.rb

# real 0.24 user 0.01 sys 0.00

m=Math.sqrt(max)
for i in 2 .. m

timex ruby sieve2.rb

# real 0.02 user 0.01 sys 0.00

timex ruby sieve1.rb 1000

# real 0.00 user 0.01 sys 0.00

timex ruby sieve2.rb 1000

# real 0.02 user 0.01 sys 0.00

Victor

On 11/6/07, George <george.ogata@gmail.com> wrote:

Hi Siep,

On Nov 6, 2007 10:14 PM, Siep Korteling <s.korteling@gmail.com> wrote:
>
> max = Integer(ARGV.shift || 100)
> sieve = []
> for i in 2 .. max
> sieve[i] = i
> end
>
> for i in 2 .. Math.sqrt(max)
> next unless sieve[i]
> (i*i).step(max, i) do |j|
> sieve[j] = nil
> end
> end
> puts sieve.compact.join(", ")
>
>
> Is Math.sqrt(max) calculated every loop?

Shouldn't be, no.

> ....
> m=Math.sqrt(max)
> for i in 2 .. m
> ....
>
> runs about 20% faster on my machine.

I'm not sure how you're benchmarking it, but I'm not seeing such
behavior with the current svn HEAD. What I did notice, however, was
that the first run of my Benchmark seemed to be noticably quicker than
the others, which I found rather odd:

user system total real
sieve1 1.080000 0.000000 1.080000 ( 1.082122)
sieve2 1.340000 0.010000 1.350000 ( 1.350781)
sieve1 1.360000 0.000000 1.360000 ( 1.362670)
sieve2 1.350000 0.010000 1.360000 ( 1.350056)

It was even more pronounced when I upped the iterations tenfold:

user system total real
sieve1 22.510000 0.050000 22.560000 ( 22.546830)
sieve2 50.500000 0.060000 50.560000 ( 50.510556)
sieve1 50.470000 0.070000 50.540000 ( 50.500493)
sieve2 50.480000 0.080000 50.560000 ( 50.503374)

If I added a call to #sieve2 (see comment in code below) before
running the timings, the benchmarks were brought back even again:

g@bang:~/tmp\$ ruby19 sieve.rb
user system total real
sieve1 1.390000 0.000000 1.390000 ( 1.392173)
sieve2 1.370000 0.000000 1.370000 ( 1.376944)
sieve1 1.400000 0.000000 1.400000 ( 1.425670)
sieve2 1.370000 0.010000 1.380000 ( 1.393410)

Somehow calling #sieve2 is slowing down subsequent calls to #sieve1.
I don't know YARV well enough yet, but I'm curious as to what's
causing this. :-/

g@bang:~/src/ruby\$ ruby19 -v
ruby 1.9.0 (2007-11-06 patchlevel 0) [i686-linux]

Regards,
George.

Code:

def sieve1
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve[i] = i
end

for i in 2 .. Math.sqrt(max)
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

def sieve2
max = Integer(ARGV.shift || 1000000)
sieve = []
for i in 2 .. max
sieve[i] = i
end

m = Math.sqrt(max)
for i in 2 .. m
next unless sieve[i]
(i*i).step(max, i) do |j|
sieve[j] = nil
end
end
end

require 'benchmark'

Benchmark.bm do |x|
# sieve2 # uncomment to remove the anomaly
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
x.report('sieve1'){sieve1}
x.report('sieve2'){sieve2}
end