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 6 of 6

Thread: Circular prime checking algorithm optimization.

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

    Default Circular prime checking algorithm optimization.

    I need help with my algorithm for finding circular primes. If you don't know what a circular prime is, it's when a number, say 179, and its rotations, 179, 917, and 791, are all prime. The algorithm simply checks if the number is a circular prime. The problem I'm using it for is finding the sum of all circular primes under 1,000,000. It's fast enough up until around 100,000, around 6 seconds. What can be done to speed it up?

    /**
    	 * @param num
    	 * @return true if the number is a circular prime
    	 * @return false if the number is not a circular prime
    	 */
    	public static boolean isCircularPrime(long num)
    	{
    		String number = Long.toString(num);//string containing the number
    		if(!isPrime(num))//false if the number isn't prime
    		{
    			return false;
    		}
    		else//checks other possibilities 
    		{
    			if(num>=10)//numbers with two or more digits can only be a circular prime if they are made of 1, 3, 7, or 9
    			{
    				if(number.contains("2")||number.contains("4")||number.contains("6")||number.contains("8")||number.contains("5")||number.contains("0"))//false if it contains a positive number, five, or zero
    				{
    					return false;
    				}
    				else//checks more if it doesn't contain an "illegal" number
    				{
    					for(int i = 0; i < number.length(); i++)//loops it for the length of the number
    					{
    						num = rotate(num);//rotates the number once
    						if(!isPrime(num))//false if the rotation isn't prime
    							return false;
    					}
    					return true;//true if it the number and all rotations are prime
    				}
    			}
    			else
    			{
    				return true;
    			}
     
    		}
     
    	}
    	//rotates the number once
    	public static int rotate(long number)
    	{
    		long start = number;
    		int numdigits = (int) Math.log10((double)number); // would return numdigits - 1
    		int multiplier = (int) Math.pow(10.0, (double)numdigits);
    		int num = 0;
    		long q = number / 10;
    		long r = number % 10;
    		//1234 = 123;
    		number = number / 10;
    		number = number + multiplier * r;
    		num = (int) number;
    		return num;
    	}

    Sieve of Eratosthenes to get a list of the primes.

    //shows all prime numbers to a specified max
    	public static int[] primesUpTo(int s) 
    	{
    		// initially assume all integers are prime
    		boolean[] isPrime = new boolean[s + 1];
    		for (int i = 2; i <= s; i++) 
    		{
    			isPrime[i] = true;
    		}
    		// mark non-primes <= N using Sieve of Eratosthenes
    		for (int i = 2; i*i <= s; i++)
    		{
    			// if i is prime, then mark multiples of i as nonprime
    			// suffices to consider mutiples i, i+1, ..., N/i
    			if (isPrime[i]) 
    			{
    				for (int j = i; i*j <= s; j++) 
    				{
    					isPrime[i*j] = false;
    				}
    			}
    		}
    		int primes = 0;
    		for (int i = 2; i <= s; i++) {
    			if (isPrime[i])
    			{
    				primes++;
    			}
    		}
    		int[] nums = new int[primes];
    		int index = 0;
    		for(int i = 2; i <= s; i++)
    		{
    			if (isPrime[i])
    			{
    				nums[index] = i;
    				index++;
    			}
     
    		}
     
    		return nums;
    	}

    I get the prime list fast enough, 32 ms. for 1,000,000.
    Last edited by aesguitar; July 25th, 2012 at 10:43 PM.


  2. #2
    Super Moderator pbrockway2's Avatar
    Join Date
    Jan 2012
    Posts
    1,069
    Thanks
    7
    Thanked 215 Times in 191 Posts

    Default Re: Circular prime checking algorithm optimization.

    What can be done to speed it up?
    One thing would be for isCircularPrime() to check for even digits as the very first thing. That would prevent half the isPrime() calls.

    Also, it occurs to me that the leading digit of the number must be the smallest digit of that number. If it isn't, then the number in question has already been checked (ie it is a rotated version of a smaller number).

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

    Default Re: Circular prime checking algorithm optimization.

    One thing would be for isCircularPrime() to check for even digits as the very first thing. That would prevent half the isPrime() calls.
    That's what this line does.

    if(number.contains("2")||number.contains("4")||number.contains("6")||number.contains("8")||number.contains("5")||number.contains("0"))//false if it contains an even number, five, or zero
    {
    	return false;
    }

    And I could figure out a way to check for the second thing you mentioned.

  4. #4
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Circular prime checking algorithm optimization.

    Quote Originally Posted by aesguitar View Post
    ... It's fast enough up until around 100,000, around 6 seconds. What can be done to speed it up?

    I get the prime list fast enough, 32 ms. for 1,000,000.
    Hmmm...I got the sieve in similar time, so our systems aren't too different. However...By adding the missing main() and isPrime() functions to your code, I got all of the circular primes (up to and including 999331) in a few hundred milliseconds.

    Now, I'm not sure why you are using longs everywhere. Since you are never going above one million, why not just use ints? That might or might not make much difference. I'm guessing there won't be major improvements, but sometimes it's more than you might guess.

    Secondly, you don't show your isPrime() function. I'm wondering why you bother to generate the array of primes. Why not just generate the sieve and let isPrime() index into the sieve array? (Isn't that the whole point of having a Sieve?)

    Something like:
    public class Whatever
    {
        static boolean [] sieve; // Instance variable used by isPrime
     
        static void generateSieve(int n) 
        {
            sieve = new boolean[n+1];
            //
            // Your code here to populate the sieve array
            //
        }
     
        static boolean isPrime(int n)
        {
            return sieve[n];
        }
     
        public static void main(String [] args)
        {
            int limit = 1000000;
            generateSieve(limit);
     
            // Take care of the first few "by inspection"
            // Loop through odd numbers after that.
            System.out.println(2);
            System.out.println(3);
            System.out.println(5);
            System.out.println(7);
            int count = 4;
     
            for (int i = 9; i <= limit; i += 2)
            {
                if (isCircularPrime(i))
                {
                    System.out.println(i);
                    ++count;
                }
            }
            System.out.printf("There are %d circular primes below %d\n", count, limit);
        }
     
     
        // Your other stuff
     
    }

    I mean, it's gotta save some time by not bothering to check even numbers greater than 2, right? Don't even bother to call isCircularPrime(), right?

    Also...

    Now, since isPrime() is so fast, thanks to the Sieve, I'm not sure that all of the tests you do inside isCircularPrime() save time. I mean they show a good analysis of what digits can't be in a circular prime, but all of those string.contains() tests (or even one of them) have got to be slower than simply indexing into an array to see whether a given number is prime (I think). If you want to experiment, maybe you can try something like

    static boolean isCircularPrime(int num)
    BEGIN
     
        Declare an int variable, temp.  Set it equal to num
     
        Make a do{}while() style loop
        LOOP
            IF temp is not prime
            THEN
                Return False
            END IF
            Do an end-around-rotate of decimal digits of temp
        WHILE (temp is not equal to num)
        //
        // The only way it leaves the bottom of the loop
        // is if all the rotations gave a prime
        // Therefore:
        Return True
     
    END isCircularPrime function

    I think the rotate function could be made without the floating point stuff, but I'm not sure the timing would be much improved by doing the rotation with a string, for example.

    Anyhow, with the appropriate isPrime() function and with isCircularPrime() implemented along the lines of the pseudo-code that I showed, I got something like 40-50 milliseconds for generating the Sieve and something around 130-150 milliseconds for the rest of the program. That's not a World Record, but it's a start.


    Cheers!

    Z
    Last edited by Zaphod_b; July 26th, 2012 at 03:05 AM.

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

    Default Re: Circular prime checking algorithm optimization.

    Here's the isPrime() function I'm using. It's brute force however it seems to be fairly fast.

    public static boolean isPrime(int num)
    	{
    		if( num == 1)
    		{
    			return false;
    		}
    		else if(num == 2)
    		{
    			return true;
    		}
    		for(int i = 2; i <= num/2 + 1; i++)
    		{
    			if(num%i==0)
    			{
    				return false;
    			}
    		}
    		return true;
    	}

    I was going to change it today. Also, the sieve only can go so high because of memory issues, only around 860,000,000. Where as that method can go as high as the maximum value for that type is.

  6. #6
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Circular prime checking algorithm optimization.

    1. If you aren't using a sieve, why did you have a sieve generator in the partial code that you posted?

    2. You said that your code was (apparently) working and you asked for suggestions to speed it up for that particular problem. How big is an array of one million and one booleans? That's the sieve size for your problem, right? I mean, a million booleans isn't much of a strain on any kind of workstation people are using these days, right?

    3. If you want to get meaningful help in the fewest number of iterations, why would you not show us (in your original post) the part that is most likely to be the bottleneck?

    4. The function in your most recent post has an int parameter. The code that you posted previously used longs. I think that getting help in the fewest number of iterations usually would require that you give us exactly what you are working on. I mean, I always test things before I offer suggestions. How the heck can I know what gives improved performance since I don't know what you are using?


    Oh, well...


    If you want a faster prime number tester that will work for all positive 32-bit integer values and doesn't involve a Sieve: Here's something that can be used with your circular prime program (after changing main() function variables to ints), and finds all of the circular primes less than a million in something like 1500 milliseconds on my machine (compared to something over 15 minutes with your brute-force isPrime and compared to roughly 150 milliseconds with a Sieve).

        static boolean isPrime(int n)
        {
     
            if (n <= 1) return false;
            if (n == 2) return true;
            if (n % 2 == 0) return false;
            if (n < 9) return true;
            if (n % 3 == 0) return false;
            if (n % 5 == 0) return false;
     
            // mods[] = {2, 3}   gives no false positives for numbers < 1,373,653
            // {31, 73} gives no false positives for numbers < 9,080,191
            //int mods[] = {2, 3};
            //int mods[] = {31, 73};
     
            // {2,7,61} gives no false positives for numbers < 4,759,123,141
            // However it will give negative for 2, 7, and 61.  2 and
            // 7 have already been taken care of.
            int mods[] = {2, 7, 61};
            if (n == 61)
            {
                return true;
            }
     
            for (int i = 0; i < mods.length; i++)
            {
                if (Witness(mods[i], n)) return false;
            }
            return true;
        }
     
     
        static boolean Witness(int a, long n)
        {
            long t = 0;
            long u = n - 1;
            while ((u & 1) == 0) {
                t++;
                u >>>= 1;
            }
     
            long xi1 = ModularExp(a, u, n);
            long xi2;
     
            for (long i = 0; i < t; i++)
            {
                xi2 = (xi1 * xi1) % n;
                if ((xi2 == 1) && (xi1 != 1) && (xi1 != (n - 1))) return true;
                xi1 = xi2;
            }
            if (xi1 != 1) return true;
            return false;
        }
     
        // Calculates (a**b) modulo n
        static long ModularExp(int a, long b, long n)
        {
            long d = 1;
            int k = 0;
            while ((b >>> k) > 0) k++;
     
            for (int i = k - 1; i >= 0; i--) {
                d = (d * d) % n;
                if (((b >>> i) & 1) > 0) d = (d * a) % n;
            }
            return d;
        }

    It starts with "Fermat's little theorem" and goes through a couple of rounds to eliminate false positives (pseudo-primes) for numbers over the entire range of (positive) 32-bit signed integers (and a little more).

    Why did I delete almost all of the comments from my prime number code? If people are interested in the theory, they can look up the procedure (I think I gave enough key words for a search engine). If they aren't interested in the theory, and if they only want something that works (or so I claim), well they wouldn't read the comments anyhow.

    Cheers,

    Z
    Last edited by Zaphod_b; July 26th, 2012 at 02:19 PM.

Similar Threads

  1. Recursive Fibonacci sequence optimization
    By aesguitar in forum Algorithms & Recursion
    Replies: 2
    Last Post: June 24th, 2012, 09:49 AM
  2. Find prime nums from 1-100 algorithm
    By The-EyE in forum What's Wrong With My Code?
    Replies: 2
    Last Post: February 5th, 2012, 11:39 PM
  3. Java Quick Sort Optimization
    By javaNewb37 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 4th, 2011, 07:32 AM
  4. A Star Pathfinding algorithm optimization
    By randomcracker in forum Algorithms & Recursion
    Replies: 4
    Last Post: May 19th, 2011, 12:11 AM
  5. Swing app gui optimization
    By nik_meback in forum AWT / Java Swing
    Replies: 1
    Last Post: December 6th, 2010, 12:55 PM