golfing Eratosthenes

Discussion in 'Ruby' started by Daniel Baird, Aug 2, 2006.

  1. Daniel Baird

    Daniel Baird Guest

    Hi all,

    I've been golfing around with the sieve of Eratosthenes. Here's what
    I've got so far:

    a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact

    It's already under 80 chars, but I'd still love to remove the
    definition of the array a, and do the whole thing with no semicolons.
    Any suggestions?

    If you're interested, here's an indented/commented copy that might
    save a few minutes..

    # create an array of integers, 2 to 100
    a=(2..100).to_a;
    p a.each{ |c|
    # for each element c in that array, if c isn't nil, it's prime. so
    set multiples of c to nil
    a.map!{ |d|
    c && d && c<d && d%c == 0 ? nil : d
    }
    }.compact # finally, print the array minus the nils


    I'd appreciate any comments.

    Cheers

    ;Daniel


    --
    Daniel Baird
    http://tiddlyspot.com (free, effortless TiddlyWiki hosting)
    http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
    Things That Suck)
    Daniel Baird, Aug 2, 2006
    #1
    1. Advertising

  2. Daniel Baird

    Daniel Baird Guest

    On 8/2/06, Daniel Baird <> wrote:
    > Hi all,
    >
    > I've been golfing around with the sieve of Eratosthenes. Here's what
    > I've got so far:
    >
    > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    >
    > It's already under 80 chars, but I'd still love to remove the
    > definition of the array a, and do the whole thing with no semicolons.
    > Any suggestions?
    >


    Improvement:

    a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}

    ..swapped to reject, and now I don't have to test for c and d being
    nil, or do the final compact. Seems ok even though I'm editing the
    array I'm looping through..

    ;D

    --
    Daniel Baird
    http://tiddlyspot.com (free, effortless TiddlyWiki hosting)
    http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
    Things That Suck)
    Daniel Baird, Aug 2, 2006
    #2
    1. Advertising

  3. On 02/08/06, Daniel Baird <> wrote:
    > Hi all,
    >
    > I've been golfing around with the sieve of Eratosthenes. Here's what
    > I've got so far:
    >
    > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    >
    > It's already under 80 chars, but I'd still love to remove the
    > definition of the array a, and do the whole thing with no semicolons.
    > Any suggestions?
    >
    > If you're interested, here's an indented/commented copy that might
    > save a few minutes..
    >
    > # create an array of integers, 2 to 100
    > a=(2..100).to_a;
    > p a.each{ |c|
    > # for each element c in that array, if c isn't nil, it's prime. so
    > set multiples of c to nil
    > a.map!{ |d|
    > c && d && c<d && d%c == 0 ? nil : d
    > }
    > }.compact # finally, print the array minus the nils
    >
    >
    > I'd appreciate any comments.
    >
    > Cheers
    >
    > ;Daniel
    >
    >
    > --
    > Daniel Baird
    > http://tiddlyspot.com (free, effortless TiddlyWiki hosting)
    > http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
    > Things That Suck)


    Here's my attempt. Note that I have made it a bit more general by
    assigning s = 100 beforehand.

    (2..(s**0.5)).inject((2..s).to_a){|a,c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact

    I got rid of the semi-colons and assigning the arrays (although
    technically it's still 'assigned' in the inject) although it might has
    made it a bit loner.

    Farrel
    Farrel Lifson, Aug 2, 2006
    #3
  4. On 02/08/06, Farrel Lifson <> wrote:
    > On 02/08/06, Daniel Baird <> wrote:
    > > Hi all,
    > >
    > > I've been golfing around with the sieve of Eratosthenes. Here's what
    > > I've got so far:
    > >
    > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    > >
    > > It's already under 80 chars, but I'd still love to remove the
    > > definition of the array a, and do the whole thing with no semicolons.
    > > Any suggestions?
    > >
    > > If you're interested, here's an indented/commented copy that might
    > > save a few minutes..
    > >
    > > # create an array of integers, 2 to 100
    > > a=(2..100).to_a;
    > > p a.each{ |c|
    > > # for each element c in that array, if c isn't nil, it's prime. so
    > > set multiples of c to nil
    > > a.map!{ |d|
    > > c && d && c<d && d%c == 0 ? nil : d
    > > }
    > > }.compact # finally, print the array minus the nils
    > >
    > >
    > > I'd appreciate any comments.
    > >
    > > Cheers
    > >
    > > ;Daniel
    > >
    > >
    > > --
    > > Daniel Baird
    > > http://tiddlyspot.com (free, effortless TiddlyWiki hosting)
    > > http://danielbaird.com (TiddlyW;nks! :: Whiteboard Koala :: Blog ::
    > > Things That Suck)

    >
    > Here's my attempt. Note that I have made it a bit more general by
    > assigning s = 100 beforehand.
    >
    > (2..(s**0.5)).inject((2..s).to_a){|a,c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    >
    > I got rid of the semi-colons and assigning the arrays (although
    > technically it's still 'assigned' in the inject) although it might has
    > made it a bit loner.
    >
    > Farrel
    >


    Gah! Excuse my atrocious spelling and grammar. "...although it has
    made it a bit longer".
    Farrel Lifson, Aug 2, 2006
    #4
  5. Daniel Baird wrote:
    > On 8/2/06, Daniel Baird <> wrote:
    > > Hi all,
    > >
    > > I've been golfing around with the sieve of Eratosthenes. Here's what
    > > I've got so far:
    > >
    > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    > >
    > > It's already under 80 chars, but I'd still love to remove the
    > > definition of the array a, and do the whole thing with no semicolons.
    > > Any suggestions?
    > >

    >
    > Improvement:
    >
    > a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}
    >
    > .swapped to reject, and now I don't have to test for c and d being
    > nil, or do the final compact. Seems ok even though I'm editing the
    > array I'm looping through..


    p (2..100).inject([]){|a,n|a.any?{|i|n%i==0}?a:a<<n}
    William James, Aug 2, 2006
    #5
  6. William James wrote:
    > Daniel Baird wrote:
    > > On 8/2/06, Daniel Baird <> wrote:
    > > > Hi all,
    > > >
    > > > I've been golfing around with the sieve of Eratosthenes. Here's what
    > > > I've got so far:
    > > >
    > > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    > > >
    > > > It's already under 80 chars, but I'd still love to remove the
    > > > definition of the array a, and do the whole thing with no semicolons.
    > > > Any suggestions?
    > > >

    > >
    > > Improvement:
    > >
    > > a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}
    > >
    > > .swapped to reject, and now I don't have to test for c and d being
    > > nil, or do the final compact. Seems ok even though I'm editing the
    > > array I'm looping through..

    >
    > p (2..100).inject([]){|a,n|a.any?{|i|n%i==0}?a:a<<n}

    p (2..100).inject([]){|a,n|a.any?{|i|n%i<1}?a:a<<n}
    William James, Aug 2, 2006
    #6
  7. Scientific calculation: get Std.Dev for a integer array

    Hi Ruby Gurus,

    Could you please point me how to do some scientific calculation in Ruby:

    1) How to calculate std.dev for an integer array?
    2) Is there a log() function in Ruby?

    Thank you!
    Austin=20
    Wang Austin-W22255, Aug 2, 2006
    #7
  8. Daniel Baird

    Sander Land Guest

    Re: Scientific calculation: get Std.Dev for a integer array

    On 8/2/06, Wang Austin-W22255 <> wrote:
    > Hi Ruby Gurus,
    >
    > Could you please point me how to do some scientific calculation in Ruby:
    >
    > 1) How to calculate std.dev for an integer array?
    > 2) Is there a log() function in Ruby?
    >
    > Thank you!
    > Austin


    1) I don't think there's a builtin function for that, so you'll have
    to create your own.
    You'll probably want to add it to the Array class.
    class Array
    def stddev
    # your function here
    end
    end

    You could also check rubyforge.org, maybe there's a statistics library
    available there.

    2) Math.log
    Sander Land, Aug 2, 2006
    #8
  9. Daniel Baird

    Paul Battley Guest

    On 02/08/06, Robert Dober <> wrote:
    > you'd love this one
    > [*2..100]


    That's lovely. Why haven't I seen it before?!

    Paul.
    Paul Battley, Aug 2, 2006
    #9
  10. Daniel Baird

    jogloran Guest

    Re: Scientific calculation: get Std.Dev for a integer array

    class Array
    def sd(ar)
    n = length
    sum_sq = inject(0.0) {|accu, v| accu + v*v}
    sum = inject(0.0) {|accu, v| accu + v}

    Math.sqrt((sum_sq - sum*sum/n) / (n-1))
    end
    end

    On 8/2/06, Sander Land <> wrote:
    > On 8/2/06, Wang Austin-W22255 <> wrote:
    > > Hi Ruby Gurus,
    > >
    > > Could you please point me how to do some scientific calculation in Ruby:
    > >
    > > 1) How to calculate std.dev for an integer array?
    > > 2) Is there a log() function in Ruby?
    > >
    > > Thank you!
    > > Austin

    >
    > 1) I don't think there's a builtin function for that, so you'll have
    > to create your own.
    > You'll probably want to add it to the Array class.
    > class Array
    > def stddev
    > # your function here
    > end
    > end
    >
    > You could also check rubyforge.org, maybe there's a statistics library
    > available there.
    >
    > 2) Math.log
    >
    >
    jogloran, Aug 2, 2006
    #10
  11. Daniel Baird

    Jan Svitok Guest

    Re: Scientific calculation: get Std.Dev for a integer array

    On 8/2/06, Wang Austin-W22255 <> wrote:
    > 1) How to calculate std.dev for an integer array?


    try GSL: http://rb-gsl.rubyforge.org/stats.html

    J.
    Jan Svitok, Aug 2, 2006
    #11
  12. On 02/08/06, William James <> wrote:
    > William James wrote:
    > > Daniel Baird wrote:
    > > > On 8/2/06, Daniel Baird <> wrote:
    > > > > Hi all,
    > > > >
    > > > > I've been golfing around with the sieve of Eratosthenes. Here's what
    > > > > I've got so far:
    > > > >
    > > > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    > > > >
    > > > > It's already under 80 chars, but I'd still love to remove the
    > > > > definition of the array a, and do the whole thing with no semicolons.
    > > > > Any suggestions?
    > > > >
    > > >
    > > > Improvement:
    > > >
    > > > a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}
    > > >
    > > > .swapped to reject, and now I don't have to test for c and d being
    > > > nil, or do the final compact. Seems ok even though I'm editing the
    > > > array I'm looping through..

    > >
    > > p (2..100).inject([]){|a,n|a.any?{|i|n%i==0}?a:a<<n}

    > p (2..100).inject([]){|a,n|a.any?{|i|n%i<1}?a:a<<n}
    >
    >
    >


    While that's an elegant looking solution it is not a 'true' sieve. It
    builds up the primes array rather than eliminating non-primes from an
    existing array.It's seems to be quite a bit slower:

    require 'benchmark'

    def build(max)
    (2..max).inject([]){|a,n|a.any?{|i|n%i<1}?a:a<<n}
    end

    def sieve(max)
    [*2..max**0.5].inject([*2..max]){|a,c|a.reject!{|d|d!=c&&d%c==0};a}
    end

    Benchmark.bm do |benchmark|
    benchmark.report("Build:"){build(ARGV[0].to_i)}
    benchmark.report("Sieve:"){sieve(ARGV[0].to_i)}
    end

    C:\Documents and Settings\flifson\My Documents>ruby primes.rb 1000
    user system total real
    Build: 0.047000 0.000000 0.047000 ( 0.047000)
    Sieve: 0.016000 0.000000 0.016000 ( 0.015000)

    C:\Documents and Settings\flifson\My Documents>ruby primes.rb 10000
    user system total real
    Build: 1.672000 0.000000 1.672000 ( 1.688000)
    Sieve: 0.359000 0.000000 0.359000 ( 0.359000)

    C:\Documents and Settings\flifson\My Documents>ruby primes.rb 100000
    user system total real
    Build: 96.437000 0.000000 96.437000 (102.107000)
    Sieve: 8.547000 0.015000 8.562000 ( 8.656000)

    Farrel
    Farrel Lifson, Aug 2, 2006
    #12
  13. Daniel Baird

    Paul Battley Guest

    On 02/08/06, Robert Dober <> wrote:
    > Enumerations, all the way ;)
    >
    > p (2..100).select{|d|!(2..d-1).find{|c|d%c==0}}


    You can shave a byte off:

    p (2..100).reject{|d|(2..d-1).find{|c|d%c==0}}

    Paul.
    Paul Battley, Aug 2, 2006
    #13
  14. Daniel Baird

    Chad Perrin Guest

    On Wed, Aug 02, 2006 at 06:20:05PM +0900, William James wrote:
    > Daniel Baird wrote:
    > > On 8/2/06, Daniel Baird <> wrote:
    > > > Hi all,
    > > >
    > > > I've been golfing around with the sieve of Eratosthenes. Here's what
    > > > I've got so far:
    > > >
    > > > a=(2..100).to_a;p a.each{|c|a.map!{|d|c&&d&&c<d&&d%c==0?nil:d}}.compact
    > > >
    > > > It's already under 80 chars, but I'd still love to remove the
    > > > definition of the array a, and do the whole thing with no semicolons.
    > > > Any suggestions?
    > > >

    > >
    > > Improvement:
    > >
    > > a=(2..100).to_a;p a.each{|c|a.reject!{|d|c<d&&d%c==0}}
    > >
    > > .swapped to reject, and now I don't have to test for c and d being
    > > nil, or do the final compact. Seems ok even though I'm editing the
    > > array I'm looping through..

    >
    > p (2..100).inject([]){|a,n|a.any?{|i|n%i==0}?a:a<<n}


    Of course, one might make a case for making that (2..99), shaving off a
    byte, since we all know 100 isn't prime. We could make that 99 lower,
    but there's no point if our point is golfing.

    --
    CCD CopyWrite Chad Perrin [ http://ccd.apotheon.org ]
    "A script is what you give the actors. A program
    is what you give the audience." - Larry Wall
    Chad Perrin, Aug 2, 2006
    #14
    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. Steve Bergman
    Replies:
    15
    Views:
    485
    Klaas
    Nov 30, 2006
  2. Phrogz

    Golfing the Farey Sequence

    Phrogz, Mar 18, 2007, in forum: Ruby
    Replies:
    6
    Views:
    193
  3. Sebastian

    Java 8 Streams and Eratosthenes

    Sebastian, Jun 4, 2013, in forum: Java
    Replies:
    22
    Views:
    617
    Sebastian
    Jun 18, 2013
Loading...

Share This Page