Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 14 of 14

Thread: Sieve of Eratosthenes: Memory & Performance

  1. #1
    Member
    Join Date
    Jun 2011
    Posts
    182
    My Mood
    Where
    Thanks
    15
    Thanked 8 Times in 8 Posts

    Default Sieve of Eratosthenes: Memory & Performance

    It appears to me that the Sieve of Eratosthenes, while easy to implement, is not at all scalable.

    If you have to create a boolean array to store all of those values in up to the limit, that begins to use obscene amounts of memory as the limit is raised. When I tried to run my Sieve algorithm with a limit of Integer.MAX_VALUE, after about 20-30 secs of computation time (slow...) I got an OutOfMemoryError.

    Is there any way to execute it more efficiently and with better performance?

    I was playing around with it to figure out how to divide and conquer the algorithm so that the JVM (or just the system if you're using C) is able to clear used memory.

    The problem is that while checking each position up to the limit, you do another walk up the tree to the limit within each iteration, so I have been unable to find a way to divide and conquer it without losing accuracy or needed records.

    Does anyone know a good way to do this?


  2. #2
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,462
    My Mood
    Hungover
    Thanks
    144
    Thanked 639 Times in 547 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    You're talking about a couple different things here.

    Your OutOfMemoryError is probably caused by trying to initialize an array that large. That's before actually filling the array with anything, or stepping through it, or doing anything related to the algorithm. To see what I mean, try running a main method that simply initializes that large an array and then prints out the first index.

    There are probably way to improve efficiency, but it really depends on what you want your output to be: if you want your output to be an array of numbers up to the limit all marked either prime or not prime, then you might be out of luck. But if you just want to output the primes, you can get rid of some of the overhead.

    This smells a bit like homework though, so I'll leave you with this, which includes some suggestions: Sieve of Eratosthenes - Wikipedia, the free encyclopedia
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Member
    Join Date
    Jun 2011
    Posts
    182
    My Mood
    Where
    Thanks
    15
    Thanked 8 Times in 8 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by KevinWorkman View Post
    You're talking about a couple different things here.

    Your OutOfMemoryError is probably caused by trying to initialize an array that large. That's before actually filling the array with anything, or stepping through it, or doing anything related to the algorithm. To see what I mean, try running a main method that simply initializes that large an array and then prints out the first index.

    There are probably way to improve efficiency, but it really depends on what you want your output to be: if you want your output to be an array of numbers up to the limit all marked either prime or not prime, then you might be out of luck. But if you just want to output the primes, you can get rid of some of the overhead.

    This smells a bit like homework though, so I'll leave you with this, which includes some suggestions: Sieve of Eratosthenes - Wikipedia, the free encyclopedia
    No this isn't homework. Programming is a hobby/planned career of mine and I love doing it.

    What I'm looking for is just randomly generating a prime number, and I would prefer not to fall back on the BigInteger class.

    This is ultimately connected to an in-development app for Android market, and I'm sort of wasting time on this so I want to get it done. The only use for it right now is generating prime hash numbers used in a hasing algorithm for a particular object.

    ADDITONAL:

    The reason I don't want to use BigInteger.getProbablePrime is that I can't find a good way to constrain the results to be within a certain range.... like 2-60 or something. I am able to do that if I write an algorithm that generates using the Sieve.
    Last edited by bgroenks96; June 7th, 2012 at 11:29 AM.

  4. #4
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,462
    My Mood
    Hungover
    Thanks
    144
    Thanked 639 Times in 547 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Do you have to calculate them on the fly each time? Just hardcode a list to contain every prime, and choose one at random when you need it- boom, randomly generated prime number.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  5. #5
    Member
    Join Date
    Jun 2011
    Posts
    182
    My Mood
    Where
    Thanks
    15
    Thanked 8 Times in 8 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by KevinWorkman View Post
    Do you have to calculate them on the fly each time? Just hardcode a list to contain every prime, and choose one at random when you need it- boom, randomly generated prime number.
    But.... that's tedious. And we're talking every prime number up to Integer.MAX_VALUE. Not just from 2-100.

    Oh and I just wanted to add I'm also self-taught with a year now of experience. Last year I spent three weeks or so doing nothing but learning Java all-day every day. And now here I am. I mean... who needs a teacher?
    Last edited by bgroenks96; June 7th, 2012 at 07:04 PM.

  6. #6
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Sieve of Eratosthenes: Memory & Performance

    You're better off repeatedly generating a random odd integer and then checking to see if it's prime. The probability of picking a prime number is quite high. See: http://en.wikipedia.org/wiki/Prime_number.

  7. #7
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,462
    My Mood
    Hungover
    Thanks
    144
    Thanked 639 Times in 547 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by bgroenks96 View Post
    But.... that's tedious. And we're talking every prime number up to Integer.MAX_VALUE. Not just from 2-100.
    I would wager you've spent more time thinking about this problem than it would take to find a listing of every prime up an arbitrarily high number (or to just use a dumb slow program that outputs them once), then write code that reads that file in. Up to you though.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  8. #8
    Member
    Join Date
    Jun 2011
    Posts
    182
    My Mood
    Where
    Thanks
    15
    Thanked 8 Times in 8 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by KevinWorkman View Post
    I would wager you've spent more time thinking about this problem than it would take to find a listing of every prime up an arbitrarily high number (or to just use a dumb slow program that outputs them once), then write code that reads that file in. Up to you though.
    But wouldn't it also take a lot of memory to store a hard coded array of prime numbers? Or if it was a file you would have to read the entire file each time, not to mention the size of the file....

  9. #9
    Crazy Cat Lady KevinWorkman's Avatar
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    5,462
    My Mood
    Hungover
    Thanks
    144
    Thanked 639 Times in 547 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by bgroenks96 View Post
    But wouldn't it also take a lot of memory to store a hard coded array of prime numbers? Or if it was a file you would have to read the entire file each time, not to mention the size of the file....
    Even if you did it by generating the array on the fly each time, you still have to deal with those issues. Actually those issues are made worse because of the overhead of whatever algorithm you go with. Storing them in a file and reading them in has no algorithmic overhead, because you did that work ahead of time. With your way, you would still have to generate the array each time.

    Reading in the file is done during loading, and I don't expect it to take very long- throw up a loading bar if it's a big deal. You mention the size of the file as a restriction- how big do you think it's going to be? How big is too big? Have you downloaded the file and tested your assumptions at all?

    With the method I'm suggesting, you can even get around reading in the whole file. Figure out how many primes you need, generate that many random numbers, then read in the prime numbers stored in those locations in the file.

    But all of this depends on your actual context. I've made my suggestion, but it's up to you. I'm not going to try to convince you to go one way or the other, but I would highly suggest actually testing your assumptions out before dismissing my suggestion. Try it out both ways and see which method suits your needs best.
    Useful links: How to Ask Questions the Smart Way | Use Code Tags | Java Tutorials
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  10. #10
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Some key statistics:

    To generate all prime numbers less than Integer.MAX_VALUE - 1, it takes ~2.4Gb of memory. On my computer (first gen i5) it takes ~2.5 minutes.

    To store all prime numbers less than Integer.MAX_VALUE - 1, it takes ~400Mb. Note that this is in binary mode (assuming 32-bit integers), if you store numbers in text mode the size will be much bigger. I kind of gave up on the time it takes to read this file in after a few minutes.

    To contrast these two methods, generating a random number and checking to see if it's prime takes on average 0.1 seconds using a naive primality checker, and 0.02 seconds using a Miller-Rabin probabilistic test. The memory consumption is around 100 bytes or less (it's O(1)).

    edit: found an optimization for generating all primes less than Integer.MAX_VALUE, takes ~70 seconds to run now (memory use is unaffected).
    Last edited by helloworld922; July 8th, 2012 at 08:21 PM.

  11. The Following 2 Users Say Thank You to helloworld922 For This Useful Post:

    copeg (June 11th, 2012), KevinWorkman (June 11th, 2012)

  12. #11
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    I believe this is what you're looking for:

    //shows all prime numbers to a specified max
    	ArrayList<Long> sieve = new ArrayList<Long>();
    	public static ArrayList<Long> primesUpTo(int n) {
    		boolean[] isPrime = new boolean[n];
    		for (int i = 0; i < n; i++) isPrime[i] = true;
    		for (int j = 2; j < isPrime.length; j++) {
    			int prime = j;
    			if (!isPrime[prime]) continue;
    			sieve.add((long) prime);
    			for (int i = prime * 2; i < isPrime.length; i = i + prime) isPrime[i]=false;
    		}
    		return sieve;
    	}

  13. #12
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,335
    Thanks
    181
    Thanked 830 Times in 773 Posts
    Blog Entries
    5

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Quote Originally Posted by aesguitar View Post
    I believe this is what you're looking for:
    Please explain how this helps answer the original poster's question.

    Helloworld gave a darn good rundown of the options, so I'd recommend taking Kevin's advice and test them to see which one works in the context you have.

  14. #13
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Sieve of Eratosthenes: Memory & Performance

    Good point copeg, is there any way to implement it into a concursive method?
    Pseudocode for dual-core:

    core0 performs the sieve up to half Integer.MAX_VALUE
    core1 performs the sieve from half Integer.MAX_VALUE

    combine the results

    then print the results.

    I guess what I'm saying is that is there any way to perform the sieve starting at a number other than 0 or 2? I've tried writing the algorithm like that, but I can't figure out how to start it from a certain point, I can only print out the primes from x to y. It still has to run through everything.

  15. #14
    Member mjr's Avatar
    Join Date
    Jan 2012
    Location
    127.0.0.1
    Posts
    36
    My Mood
    Fine
    Thanks
    8
    Thanked 2 Times in 1 Post

    Default Re: Sieve of Eratosthenes: Memory & Performance

    I've actually written a small program (it was for a homework assignment in a college Java class I took) that actually checked for Prime numbers, and did it fairly quickly.

    In fact, I found a list of primes in the range of two to the max integer value (used a Google search). I was able to iterate over the values (starting at 2), evaluate whether or not it was prime, and if it was, write it to a file. That all happened in under a second.

    Here's a hint:

    Use a square root. If the number you're checking (say, 25) has a whole number, integer square root (square root of 25 is 5), then the number you're checking is not, by definition, prime. If the number you're checking has a decimal square root, to check to see if it is prime, all you have to do is iterate, dividing the number you're checking by the next number in line.

    As an example, sqrt(101) = 10.0498756

    So take 101, and divide it by 2, 3, 4, up to 10. If it divides by any of those evenly, then it's not prime.

    There are other tricks, but I think this will help you get started.

    Also, recall the the only even prime number is 2.

Similar Threads

  1. CPU Performance Software.
    By Mr.777 in forum Java Theory & Questions
    Replies: 11
    Last Post: September 30th, 2011, 01:10 AM
  2. sieve of eratosthenes
    By rsala004 in forum Collections and Generics
    Replies: 5
    Last Post: December 29th, 2010, 09:37 AM
  3. Memory Handling -de allocate memory in Java
    By 19world in forum Java Theory & Questions
    Replies: 4
    Last Post: June 15th, 2010, 04:05 AM
  4. Cracking password in less number of Trials using brute forcea
    By xisstar in forum What's Wrong With My Code?
    Replies: 2
    Last Post: June 10th, 2009, 10:40 AM
  5. Replies: 1
    Last Post: May 13th, 2008, 08:08 AM