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