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.
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?
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:
I think it runs in quadratic time.
Paul Beckett wrote: . . . the time taken is relative to the performance of the machine. . . .
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.
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
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.
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.
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".
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.
I don't think Project Euler do want speed above all else. I think they want us to think up a correct solution.
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 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.
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.
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.
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.