sieve.rb sample

Discussion in 'Ruby' started by Siep Korteling, Nov 6, 2007.

  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
    end

    for i in 2 .. Math.sqrt(max)
    next unless sieve
    (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/.
     
    Siep Korteling, Nov 6, 2007
    #1
    1. Advertising

  2. Siep Korteling

    George Guest

    Hi Siep,

    On Nov 6, 2007 10:14 PM, Siep Korteling <> wrote:
    >
    > max = Integer(ARGV.shift || 100)
    > sieve = []
    > for i in 2 .. max
    > sieve = i
    > end
    >
    > for i in 2 .. Math.sqrt(max)
    > next unless sieve
    > (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
    end

    for i in 2 .. Math.sqrt(max)
    next unless sieve
    (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
    end

    m = Math.sqrt(max)
    for i in 2 .. m
    next unless sieve
    (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
     
    George, Nov 6, 2007
    #2
    1. Advertising

  3. Siep Korteling

    Victor Reyes Guest

    Note: parts of this message were removed by the gateway to make it a legal Usenet post.

    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 <> wrote:
    >
    > Hi Siep,
    >
    > On Nov 6, 2007 10:14 PM, Siep Korteling <> wrote:
    > >
    > > max = Integer(ARGV.shift || 100)
    > > sieve = []
    > > for i in 2 .. max
    > > sieve = i
    > > end
    > >
    > > for i in 2 .. Math.sqrt(max)
    > > next unless sieve
    > > (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
    > end
    >
    > for i in 2 .. Math.sqrt(max)
    > next unless sieve
    > (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
    > end
    >
    > m = Math.sqrt(max)
    > for i in 2 .. m
    > next unless sieve
    > (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
    >
    >
     
    Victor Reyes, Nov 6, 2007
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Philip Smith

    Multiple Polynomial Quadratic Sieve

    Philip Smith, May 30, 2006, in forum: Python
    Replies:
    2
    Views:
    535
    Philip Smith
    May 30, 2006
  2. Steve Bergman
    Replies:
    15
    Views:
    529
    Klaas
    Nov 30, 2006
  3. jzakiya
    Replies:
    3
    Views:
    584
    jzakiya
    Jul 19, 2008
  4. jzakiya
    Replies:
    4
    Views:
    512
    user923005
    Jun 13, 2008
  5. jzakiya
    Replies:
    6
    Views:
    216
    Michael Ulm
    Jun 11, 2008
Loading...

Share This Page