Sieve.rb sample

Ruby
1

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.

2

Hi Siep,

On Nov 6, 2007 10:14 PM, Siep K. [email protected] wrote:

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

3

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