Results 1 to 15 of 15
Like Tree1Likes
  • 1 Post By AndrewM16921

Thread: My program has to run in less than a minute. Can anyone help make my code efficient?

  1. #1
    jamgor is offline Member
    Join Date
    Jun 2013
    Posts
    12
    Rep Power
    0

    Default My program has to run in less than a minute. Can anyone help make my code efficient?

    Hey all. I am trying to find the millionth prime number. My code's functionality is fine, but it takes too long to run (about 3 minutes)

    I want to make it run in about a minute or less. Here's my code:

    Java Code:
    import java.util.*;
    public class Mainn
    {
    
    public static void main(String[] args)
    { 
    
    	int count = 0; 
    	int number = 2; 
    	ArrayList <Integer> a = new ArrayList();
    	
    	while(count < 1000000)
    	{
    		int c=0; 
    		for(int i = 2; i <= Math.sqrt(number) ; i++)
    		{	 
    			if (number%i == 0) //check to see if it is even
    			{ 
    				c=1;
    				break; //end loop if even
    			}
    		}
    		if(c==0)
    		{ 
    			a.add(number);
    			count++;
    		} 
    
    		number++;
    	}//end of while 
    	System.out.println(a.get(a.size()-1)); //prints last element of the arraylist which is the 1 millionth prime number
    
    		 long startTime = System.currentTimeMillis();
            long total = 0;
            for (int i = 0; i < 1000000; i++)
            {
                total += i;
        }
            long endTime = System.currentTimeMillis();
            System.out.println("Runtime = " + (endTime-startTime) + " milliseconds");
    
    	
    } //end of main 
    }
    Thanks!

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Use a 'Sieve of Eratosthenes' and a BitSet; Google is your friend here.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    jamgor is offline Member
    Join Date
    Jun 2013
    Posts
    12
    Rep Power
    0

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    ^ I'm not allowed to use that algorithm haha!

  4. #4
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    One small note.

    Math.sqrt() is relatively expensive, try comparing i*i <= number, instead.

    This is the change for me running your program (moved startTime to top of main, also) before and after that change (on average, it takes half the time):

    BEFORE: Runtime = 22081 milliseconds
    AFTER: Runtime = 10915 milliseconds

  5. #5
    jamgor is offline Member
    Join Date
    Jun 2013
    Posts
    12
    Rep Power
    0

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Quote Originally Posted by AndrewM16921 View Post
    One small note.

    Math.sqrt() is relatively expensive, try comparing i*i <= number, instead.

    This is the change for me running your program (moved startTime to top of main, also) before and after that change (on average, it takes half the time):

    BEFORE: Runtime = 22081 milliseconds
    AFTER: Runtime = 10915 milliseconds
    It did speed up by about half. Wow, thank you! What's so bad about math.sqrt()?

  6. #6
    jamgor is offline Member
    Join Date
    Jun 2013
    Posts
    12
    Rep Power
    0

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Having just learned what a hashmap is, would it be more efficient than an arraylist here?

  7. #7
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    HashMap is good if you're searching for items in a collection (or HashSet, in this case). But if you're just iterating through the list linearly, an ArrayList is ideal.

    Also, keep in my that when it comes to these data structures (Sets, and HashMap) the ordering of the data is not necessarily preserved and duplicates are overwritten.

    Not sure exactly, but I know the algorithms for calculating a square root are WAY more intense than those for simply multiplying 2 numbers. :P

    If you ever see a lot of physics engines or games, they often used the squared value rather than the actual value for distance comparisons. This is why vector type classes have a distance() method as well as a distanceSquared() method - for performance.
    Last edited by AndrewM16921; 06-13-2013 at 03:06 AM.

  8. #8
    jamgor is offline Member
    Join Date
    Jun 2013
    Posts
    12
    Rep Power
    0

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Quote Originally Posted by AndrewM16921 View Post
    HashMap is good if you're searching for items in a collection (or HashSet, in this case). But if you're just iterating through the list linearly, an ArrayList is ideal.

    Also, keep in my that when it comes to these data structures (Sets, and HashMap) the ordering of the data is not necessarily preserved and duplicates are overwritten.

    Not sure exactly, but I know the algorithms for calculating a square root are WAY more intense than those for simply multiplying 2 numbers. :P

    If you ever see a lot of physics engines or games, they often used the squared value rather than the actual value for distance comparisons. This is why vector type classes have a distance() method as well as a distanceSquared() method - for performance.
    Awesome explanation there :)
    Also, math.sqrt() takes longer because it's a method right or I'll just go with your explanation?
    Last edited by jamgor; 06-13-2013 at 03:25 AM.

  9. #9
    AndrewM16921 is offline Senior Member
    Join Date
    Jan 2009
    Location
    CA, USA
    Posts
    264
    Rep Power
    6

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Lol, not exactly. Let me put it this way. In OpenJDK, sqrt is defined like this:
    (note it's native code, not java code)

    Java Code:
    JNIEXPORT jdouble JNICALL
    Java_java_lang_StrictMath_sqrt(JNIEnv *env, jclass unused, jdouble d)
    {
        return (jdouble) jsqrt((double)d);
    }
    Java Code:
    #ifdef __STDC__
            double sqrt(double x)           /* wrapper sqrt */
    #else
            double sqrt(x)                  /* wrapper sqrt */
            double x;
    #endif
    {
    #ifdef _IEEE_LIBM
            return __ieee754_sqrt(x);
    #else
            double z;
            z = __ieee754_sqrt(x);
            if(_LIB_VERSION == _IEEE_ || isnan(x)) return z;
            if(x<0.0) {
                return __kernel_standard(x,x,26); /* sqrt(negative) */
            } else
                return z;
    #endif
    }
    Java Code:
     /* generate sqrt(x) bit by bit */
            ix0 += ix0 + ((ix1&sign)>>31);
            ix1 += ix1;
            q = q1 = s0 = s1 = 0;   /* [q,q1] = sqrt(x) */
            r = 0x00200000;         /* r = moving bit from right to left */
    
            while(r!=0) {
                t = s0+r;
                if(t<=ix0) {
                    s0   = t+r;
                    ix0 -= t;
                    q   += r;
                }
                ix0 += ix0 + ((ix1&sign)>>31);
                ix1 += ix1;
                r>>=1;
            }
    
            r = sign;
            while(r!=0) {
                t1 = s1+r;
                t  = s0;
                if((t<ix0)||((t==ix0)&&(t1<=ix1))) {
                    s1  = t1+r;
                    if(((t1&sign)==sign)&&(s1&sign)==0) s0 += 1;
                    ix0 -= t;
                    if (ix1 < t1) ix0 -= 1;
                    ix1 -= t1;
                    q1  += r;
                }
                ix0 += ix0 + ((ix1&sign)>>31);
                ix1 += ix1;
                r>>=1;
            }
    
        /* use floating add to find out rounding direction */
            if((ix0|ix1)!=0) {
                z = one-tiny; /* trigger inexact flag */
                if (z>=one) {
                    z = one+tiny;
                    if (q1==(unsigned)0xffffffff) { q1=0; q += 1;}
                    else if (z>one) {
                        if (q1==(unsigned)0xfffffffe) q+=1;
                        q1+=2;
                    } else
                        q1 += (q1&1);
                }
            }
            ix0 = (q>>1)+0x3fe00000;
            ix1 =  q1>>1;
            if ((q&1)==1) ix1 |= sign;
            ix0 += (m <<20);
            __HI(z) = ix0;
            __LO(z) = ix1;
            return z;
    }
    And nope, I have no idea what's going on there ^
    jamgor likes this.

  10. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Quote Originally Posted by jamgor View Post
    ^ I'm not allowed to use that algorithm haha!
    Very funny indeed; you want one of the fastest algorithms but you're now allowed (by who?) to use a very efficient algorithm; beside that fiddiling with the Math.sqrt(x) method, note that all primes are of the form 6*n-1 or 6*n+1 (except 2 and 3); you can use that fact in your loop for an additional speed up.

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,534
    Rep Power
    5

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Also, don't divide by every integer up to the square root of the number. Only divide by the primes you have already computed < square root of the number. And don't use System.currentTimeMillis() to time your result. Use System.nanoTime().

    Regards,
    Jim
    Last edited by jim829; 06-13-2013 at 05:20 PM.
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Quote Originally Posted by jim829 View Post
    Also, don't divide by every integer up to the square root of the number. Only divide by the primes you have already computed < square root of the number.
    That's a sieve and the OP is not allowed to use it (for reasons that are beyond me).

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  13. #13
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,534
    Rep Power
    5

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Hmm, I implemented Eratosthenes' sieve many years ago but I didn't equate that to what I just recommended. I was just applying the fundamental theorem of arithmetic. I wonder if the OP is allowed to only check odd numbers > 2?

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

  14. #14
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Quote Originally Posted by jim829 View Post
    Hmm, I implemented Eratosthenes' sieve many years ago but I didn't equate that to what I just recommended. I was just applying the fundamental theorem of arithmetic. I wonder if the OP is allowed to only check odd numbers > 2?
    Think of the 'classic' sieve: you take the next number that is definitely prime and mark out all multiples thereof; you start with number 2 (definitely a prime). Compare this with what you suggested ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  15. #15
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    3,534
    Rep Power
    5

    Default Re: My program has to run in less than a minute. Can anyone help make my code efficie

    Well, I found this on Wiki and started to read some of the footnote references:

    "Trial division can be used to produce primes by filtering out the composites found by testing each candidate number for divisibility by its preceding primes. It is often confused with the sieve of Eratosthenes, although the latter directly generates the composites instead of testing for them. Trial division has worse theoretical complexity than that of the sieve of Eratosthenes in generating ranges of primes.[2]

    When testing each candidate number, the optimal trial division algorithm uses just those prime numbers not exceeding its square root. The widely known 1975 functional code by David Turner[9] is often presented as an example of the sieve of Eratosthenes[8] but is actually a sub-optimal trial division algorithm.[2]"

    I read parts of the paper cited in the article in [2] above. It discusses a way of actually using the sieve to compute primes with an infinite upper bound. I may have to try it out.

    Regards,
    Jim
    The Java™ Tutorial | SSCCE | Java Naming Conventions
    Poor planning our your part does not constitute an emergency on my part.

Similar Threads

  1. Replies: 5
    Last Post: 03-14-2013, 11:39 AM
  2. The Most Efficient Way To Make a 2D Game?
    By TacoManStan in forum New To Java
    Replies: 5
    Last Post: 01-26-2012, 08:57 PM
  3. How to make my program more efficient?
    By LonelyClock in forum New To Java
    Replies: 9
    Last Post: 11-29-2011, 04:47 AM
  4. more efficient way to make this??? [LOOK]
    By Green in forum New To Java
    Replies: 10
    Last Post: 09-09-2011, 01:01 AM
  5. Replies: 1
    Last Post: 03-22-2010, 08:21 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •