golfing Eratosthenes

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

1. Daniel BairdGuest

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

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

2. Daniel BairdGuest

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

3. Farrel LifsonGuest

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
>
>
>
> 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

Farrel
Farrel Lifson, Aug 2, 2006
4. Farrel LifsonGuest

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
Farrel Lifson, Aug 2, 2006
5. William JamesGuest

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
6. William JamesGuest

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
7. Wang Austin-W22255Guest

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
8. Sander LandGuest

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
You'll probably want to add it to the Array class.
class Array
def stddev
end
end

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

2) Math.log
Sander Land, Aug 2, 2006
9. Paul BattleyGuest

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
10. jogloranGuest

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
> You'll probably want to add it to the Array class.
> class Array
> def stddev
> end
> end
>
> You could also check rubyforge.org, maybe there's a statistics library
> available there.
>
> 2) Math.log
>
>
jogloran, Aug 2, 2006
11. Jan SvitokGuest

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
12. Farrel LifsonGuest

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
13. Paul BattleyGuest

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

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