aspose file tools*
The moose likes Beginning Java and the fly likes Sieve of Eratosthenes Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Sieve of Eratosthenes" Watch "Sieve of Eratosthenes" New topic
Author

Sieve of Eratosthenes

Gauri Shankar Iyer
Greenhorn

Joined: Feb 23, 2009
Posts: 6
My first attempt at writing the algo for finding primes in a range using the Sieve of Eratosthenes.
(Wikipedia: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

I'm wondering what are the bad practices you can see in this small piece of code, and any optimizations you see fit? Also, looking to reduce the number of lines of code in any way possible. Some criticism will be very helpful. Thanks.

Some observations you might find interesting:

- For the range (1, 500000), it takes about 5 seconds with the code below, on my AMD dual core machine.
- On line 33, changing the Math.pow(variable, 2) to (variable * variable) reduces the running time to 2 seconds!
- The reduction of lines 59, 60, 61 into line 62 has no effect whatsoever. Removing explicit allocations doesn't necessarily mean implicit VM allocations will be removed too.

Hunter McMillen
Ranch Hand

Joined: Mar 13, 2009
Posts: 492

any sort of built-in operators (*,/,+,-) are always going to be less expensive to use than recursive functions like Math.pow, because functions have to be called, execute their own code and possibly call other functions, then they have to return. And for a smaller program you can never tell the difference. But when you are trying to do 500,000 calculations, that overhead adds up quickly.


Hunter


"If the facts don't fit the theory, get new facts" --Albert Einstein
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
Always use x * x rather than Math.pow(x, 2). It is more precise, as well as faster.
Lester Burnham
Rancher

Joined: Oct 14, 2008
Posts: 1337
"end < start || start == end" is the same as "end <= start"
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
It is a long time since I wrote a sieve application, but yours looks much more complicated than I remember mine.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4422
    
    8

Interesting comment on line 43 .
Gauri Shankar Iyer
Greenhorn

Joined: Feb 23, 2009
Posts: 6
Matthew Brown wrote:Interesting comment on line 43 .

Ha ha, isn't that a remarkable trait of most programmers?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
I wrote mine with a boolean[] array. Set all the values to true (except 0 and 1, which are implicitly false) and change all the places found with the sieve to false. Start looping at 2. It is easier to have an array 1 size larger than your range, so you can use the index to represent the number.
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
see problem 10 "Calculate the sum of all the primes below two million" on projecteuler.net. If you can solve the problem then a solution pdf is provided giving hints (including pseudo code) for how to efficiently do a sieve (solves in much less than a second on a modest PC). Your code should be more than sufficient to solve the problem and is way more efficient than my first attempt where I didn't even use a sieve. The solution pdf will explain things much more eloquently than I could here.

Note: Campbell is correct to use a boolean[] but this can be optimized even further thus reducing the size of the array.
(i) no even number other than 2 can be a prime
(ii) can you reduce the max number you need to check for?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
I tried it with a boolean[] array yesterday, taking about 3 seconds to sieve from 2 to 100000000 (1e8), but it took about 1 minute to display all those numbers on screen. For 2 to 1000000000 (1e9) I suffered an OutOfMemoryError.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
Paul Beckett wrote: . . . Campbell is correct . . .
Can I have that in writing please
can you reduce the max number you need to check for?
I think the squaring allows for that. But surely it is simpler to use the square root?
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
I think the squaring allows for that. But surely it is simpler to use the square root?

ok, I'd missed that bit
Using the square root would be more efficient in this case. So work out the square root of the end number (crosslimit) before the loop and then the termination expression becomes "end<crosslimit".

Using a boolean array you can change your increment expression to increment the loop by the number you are currently removing multiples of (runningPrime in the original code).

My algorithm takes <1.5 seconds to work out all the primes 1e8 but also gets an OutOfMemoryError with 1e9. Obviously the time taken is relative to the performance of the machine.

My version of the sieve:
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
Paul Beckett wrote: . . . the time taken is relative to the performance of the machine. . . .
I think it runs in quadratic time.

Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?
I seemed to get a different result from yours when I printed the numbers out.
~/java$ java Eratosthenes
Time for sieving 0.001s Please push "enter" to continue.
Primes found:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Total of all those primes = 1060

Duration by Paul's method = 0.002s
Please push "enter" to continue.
Primes found by Paul's method:
4 7 10 12 13 16 17 19 22 24 25 27 28 31 32 34 37 38 40 42 43 45 46 47

Total of all those primes = 659
Kurt Van Etten
Ranch Hand

Joined: Sep 07, 2010
Posts: 98
Campbell Ritchie wrote:I tried it with a boolean[] array yesterday, taking about 3 seconds to sieve from 2 to 100000000 (1e8), but it took about 1 minute to display all those numbers on screen. For 2 to 1000000000 (1e9) I suffered an OutOfMemoryError.


Well, that raises some interesting questions... How much memory does the Java VM use to store a boolean value? I'm guessing one byte on most platforms. (Does Java have anything similar to the C sizeof operator? It would be nice to be able to estimate available resources before attempting a memory allocation.) In that case, you could increase the range of your sieve by using bitwise operators to store 8 0/1 values per byte, with a bit of a performance trade-off.

Of course that would only increase your range by a factor of 8. To get a truly big sieve, you'd need to write the values out to disk. With some judicious buffering and separate threads to handle the I/O, the performance should still be reasonable.
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
Campbell Ritchie wrote:Are you using false == prime? If so, what about 0, which is an exact multiple of every number, but is not a "natural" number? And what about 1, which doesn't divide by any other numbers, but is not usually considered prime?
I seemed to get a different result from yours when I printed the numbers out.

I didn't include it before but my summing is done like so:


So a prime is false, don't think it matters which way round you do it. With prime = false then I don't need to explicitly set every value in the array to true before sieving.
The array doesn't contain even numbers so have to handle 2 as a special case. Other than that the value in the array at index i represents the number 2i+1, so index 3 represents the number 7.
Where maxNumber=12:
sieve: [false, false, false, false, true]
index: [ 0, 1, 2, 3, 4]
numbers: [ 1, 3, 5, 7, 9]
Obviously 1 is not a prime number so notice that when iterating the sieve always start at index 1.

Also my sieveBound should have been limit/2 instead of "(limit-1)/2".
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
So what did I copy wrongly that I got your code to produce that series of numbers?
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
you didn't copy anything incorrectly. The implementation you have used of my version of the sieve is correct I think. It is the printPrimes method that is incorrect. You are printing out the index of any "true" in the array. Whereas in my implementation of the sieve, "false" is a prime. And then instead of the index of the "false" elements you need to use 2i+1 to find the real number and start iterating at index 1.

Obviously you have identified a big flaw in the method I've used - its difficult to understand what is going on!!! However this is a java implementation of the method from Project Euler problem 10 solution pdf (section 10.2.2). I prefer to make code readable as a first priority and then only reduce readability to optimise if absolutely necessary but for project euler execution speed seems to be the priority over all others.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39415
    
  28
Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers. If I had seen an output of all non-prime numbers, I would quickly have worked out that I was printing the wrong half of the array.
I don't think Project Euler do want speed above all else. I think they want us to think up a correct solution.
Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
Campbell Ritchie wrote:Please post working code, which we can actually execute and understand the output of. You ought to have posted the printing method as well, so we can see a set of prime numbers

The sieve I posted in my second post is a fully functioning sieve minus the method declarations.
My version of the sieve was for solving the project euler problem 10 and doesn't need a printing method for that purpose. In my third post I did provide the complete summing functionality which shows how to convert an array element to a prime number. Also I provided a "diagram" of the sieve, the array indexes, and the corresponding number the array index represented.
Carey Brown
Ranch Hand

Joined: Nov 19, 2001
Posts: 188

I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast. On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds.

Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast.

Yeah - boolean[] arrays seem to often be implemented using 8 bits for each boolean. The boolean array is faster, but not by enough to justify using eight times as much memory (IMO).

Carey Brown wrote: On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds

On my machine, it ran in 0.02 sec as well. And the same code can run 500,000,000 numbers in 18-19 sec. (Going to 1,000,000,000 would require changing the standard JVM memory settings, so I stopped there.) I got it down to 11-12 sec by replacing the second for loop with this:

As long as you've already handled all the multiples of 2, we might as well only deal with the odd multiples of i at this point.

A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.
Kurt Van Etten
Ranch Hand

Joined: Sep 07, 2010
Posts: 98
Carey Brown wrote:I'll just add my 2cents. Using a BitSet should help with memory issues and appears to be plenty fast. On my machine (your milage may vary) I ran 500,000 numbers in 0.02 seconds.


I was curious about how big of a time hit this would make, so I switched my previous version to use a BitSet instead of an array (keeping everything else the same), and it took about 2.5 times longer to run. So I suppose you have to weigh whether the time or memory is more important to you. Now I wonder how much of the time hit is due to the overhead for the function calls. I ought to try implementing the bit operations directly in an array and see how much of an improvement that makes.
Kurt Van Etten
Ranch Hand

Joined: Sep 07, 2010
Posts: 98
Mike Simmons wrote:A next step might be to eliminate all multiples of 2 or 3. My guess is that might reduce the time by about 1/6 (since the only new skips are for multiples of 3 which aren't already multiples of 2, like 9, 15, 21, 27, 33... etc). Making the code somewhat more complex to boot. Not sure it's worth it. But I thought I'd toss it out there; maybe someone can use the idea to good effect.


I tried this out. Instead of adding 2 times the current prime each time you mark an element in the sieve, you alternate adding 4 times and 2 times the current prime. Unfortunately the time was essentially unchanged--even though I needed to mark 1/3 fewer elements in the sieve for each prime greater than 3, the time savings was apparently offset by the slight increase in complexity.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Yeah, I was getting very similar results, with the same skip-2/skip-4 idea. Seems like the added calculations to figure out which elements to hit offset the savings of hitting fewer elements. Annoying. I was looking for cleaner ways to refactor it, but not seeing much improvement. Oh well.

Paul Beckett
Ranch Hand

Joined: Jun 14, 2008
Posts: 96
The BitSet is more efficient in terms of memory usage - no argument there. However both BitSet and boolean[] will hit the limit soon enough of being indexed by an int.

Arbitrarily allocating Xmx768m, my boolean[] can handle 1e9 in 15s with the BitSet in 36s. The point being 1e9 is approximately half of Integer.MAX_VALUE. So why did I stop at 1e9 and not go on to Integer.MAX_VALUE? My implementation doesn't contain even numbers in the sieve so requires an i*2 calculation to work out the real number from the index (see earlier posts) so 1e9 is approximately the max value I can handle without recoding. So with recoding then memory requirement would be fulfilled by Xms1536m. I'm not advocating always chucking more memory at a problem but in this instance IMHO the inherent Integer.MAX_VALUE limit is more of a concern than the memory efficiency.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Sieve of Eratosthenes