# Sieve.rb sample

**URL:** <https://www.ruby-forum.com/t/sieve-rb-sample/119362>\
**Category:** Ruby\
**Created:** [November 6, 2007, 12:14pm UTC](https://www.ruby-forum.com/t/sieve-rb-sample/119362 "2007-11-06T12:14:56Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![steenslag](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c57346/32.png) [@steenslag](https://www.ruby-forum.com/u/steenslag)\
**Post date:** [November 6, 2007, 12:14pm UTC](https://www.ruby-forum.com/t/sieve-rb-sample/119362/1 "2007-11-06T12:14:56Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![steenslag](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c57346/32.png) [@steenslag](https://www.ruby-forum.com/u/steenslag)\
**Post date:** [November 6, 2007, 5:22pm UTC](https://www.ruby-forum.com/t/sieve-rb-sample/119362/2 "2007-11-06T17:22:30Z")

</div>

Hi Siep,

On Nov 6, 2007 10:14 PM, Siep K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![steenslag](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/s/c57346/32.png) [@steenslag](https://www.ruby-forum.com/u/steenslag)\
**Post date:** [November 6, 2007, 5:56pm UTC](https://www.ruby-forum.com/t/sieve-rb-sample/119362/3 "2007-11-06T17:56:25Z")

</div>

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