Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Seive of Eratosthenes optimizing
Author Message
Insectoid

Posted: Thu Apr 15, 2010 4:51 pm   Post subject: Seive of Eratosthenes optimizing

I found the Sieve of Eratosthenes algorithm, and decided to write one myself. It works, but it's really, really slow calculating primes up to anything higher than 100000. I want to make it as fast as possible. Anyway, here's my code:

 Ruby: #Seive of Eratosthenes #Finds Prime Numbers print "Enter the last number to check (greater than 1): " max_int = gets.to_i list = (2..max_int).to_a #(2..Math.sqrt(max_int).to_i).to_a.each do |n| list.each do |n| #n will only ever be a prime number puts "Prime Found: #{n}\n Deleting multiples of #{n}..."         if n**2 > max_int then #Quits once n squared is greater than max_int (only primes will be left)                 puts "Sieve complete..."                 break         end                 list.each_index do |i|                         if (list[i] % n == 0) && (list[i] != n) then #Checks if list[i] is divisable by n (but not equal to it, n is prime)                         #puts "Deleting: #{list[i]}"                         list.slice!(i) #deletes list[i]                  end         end end #This won't be necessary later. Once I delete extra puts above I'll delete this. puts "Primes up to #{max_int}:" list.each do |i|         puts i end

I figure, if I can change
 code: list.each_index do |i|

to start at element [i]n
+1 (all previous elements are prime) I can drop the 2nd condition out of
 code: if (list[i] % n == 0) && (list[i] != n) then

Which should significantly speed up the script (that conditional is run 849117 of times when max_int = 100000, whereas that loop is only tested 65 times)

I tried changing the loop to
 code: list.slice(1..-1).each_index do |i|

but that causes a syntax error (dunno if -1 is valid in that scenario...). I also tried
 code: list.slice(1..list.length-1).each_index do |i|

but that throws the same error.

If anyone could help me execute that loop without passing the first element in list (in a non-hackish manner), please do!

Brightguy

Posted: Thu Apr 15, 2010 6:55 pm   Post subject: Re: Seive of Eratosthenes optimizing

Insectoid @ Thu Apr 15, 2010 4:51 pm wrote:
Which should significantly speed up the script (that conditional is run 849117 of times when max_int = 100000, whereas that loop is only tested 65 times)

That conditional isn't of much concern: it's only O(1). (And BTW, you could actually use a list[i] >= n^2 condition). If you want to be efficient, don't use Ruby's split inside the loop! Have you seen the code for even delete_at? It's O(N)! Also checking every element in the list for divisibility is quite needlessly inefficient.
Tony

Posted: Thu Apr 15, 2010 7:06 pm   Post subject: RE:Seive of Eratosthenes optimizing

Quote:

list.each_index do |i|

if (list[i] % n == 0) && (list[i] != n) then

There's a _much faster_ way of getting the same list of values, without doing any comparisons. (modulo is expensive in a loop)

Quote:

list.slice!(i) #deletes list[i]

There's a _much faster_ way to mark a number as prime or not, than taking it out of a list.

Currently, your list.include? is O(N). You want to be able to check if the number is prime in O(1), once you build that list.
Tony's programming blog. DWITE - a programming contest.
Insectoid

Posted: Thu Apr 15, 2010 7:13 pm   Post subject: RE:Seive of Eratosthenes optimizing

Brightguy, I did try delete_at after posting this, but figured out something else that might be faster, which your post moots anyway. So delete_at might be the thing.

Tony, I don't see what you're getting at. I'll take your bolded 'mark' as a hint.
Brightguy

Posted: Thu Apr 15, 2010 7:29 pm   Post subject: Re: RE:Seive of Eratosthenes optimizing

Insectoid @ Thu Apr 15, 2010 7:13 pm wrote:
Brightguy, I did try delete_at after posting this, but figured out something else that might be faster, which your post moots anyway. So delete_at might be the thing.

I was pointing out how bad it is. The O(N) call inside your loop is terrible to your efficiency.
Insectoid

Posted: Thu Apr 15, 2010 7:30 pm   Post subject: RE:Seive of Eratosthenes optimizing

ah, heh.

*Insectoid hasn't looked up Big-O notation and so is just assuming that O(N) is significantly worse than O(1).
chrisbrown

Posted: Thu Apr 15, 2010 7:51 pm   Post subject: RE:Seive of Eratosthenes optimizing

To put it loosely, if N is the size of your input, runtime can be estimated by counting the number of operations as a function of N. O(1) means as N grows large, the time it takes to perform whatever you're looking at is constant - a good thing. O(N) is a linear relationship. O(N^2) gets large faster than O(N), so it is worse and is very poor for large inputs.
Brightguy

Posted: Thu Apr 15, 2010 7:51 pm   Post subject: Re: RE:Seive of Eratosthenes optimizing

This is abusing the notation, but if you want a better feeling than "significantly worse", here it means that computing the primes to 100,000 takes you about 100,000 times longer.

Insectoid

Posted: Thu Apr 15, 2010 7:57 pm   Post subject: RE:Seive of Eratosthenes optimizing

Ah. Well. That makes sense. I did notice incredible slowdowns at higher numbers (500 000 took over 100 times as long as 100 000). Damn.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 9 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: