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.length1).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 nonhackish manner), please do! 





Sponsor Sponsor



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





Sponsor Sponsor



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. 






