Results 1 to 4 of 4

Thread: Sieve of Atkin Multithreading

  1. #1
    Join Date
    Feb 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Sieve of Atkin Multithreading

    I am taking a class on multithreading in java. My project is to implement Sieve of Atkin in multithreading. But I have a small little problem and I am assuming it has to do with thread safety. Sieve of Atkin counts prime numbers from 0 to N using some math trickery to become super efficient. My problem is I seem to get 3 to 4 different answers depending on each run. Can anyone point me in the right direction or see an obvious error it would be greatly appreciated

    Code:
    // SieveOfAtkin.java
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    import java.util.concurrent.Callable;
    import java.util.concurrent.ExecutorService;
    import java.util.concurrent.Executors;
    import java.util.concurrent.TimeUnit;
    
    
    public class SieveOfAtkin {
    final static int N = 10000000;
    
    private static int limitSqrt = (int)Math.sqrt((double)N);
    final static boolean[] isPrime = new boolean[N + 1];
    public static void main(String[] args) {
    	long StartingTime = System.currentTimeMillis();
        long end = sieveOfAtkin();
        System.out.println((end-StartingTime)/1000.);
    }
    private static long sieveOfAtkin() {
    	Arrays.fill(isPrime, false);
    
        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;
        isPrime[3] = true;
    
    	final List<Callable<Integer>> partitions = new ArrayList<Callable<Integer>>(); 
        for (int x = 1; x <= limitSqrt; x++) {
    		final int start = x;
    		partitions.add(new Callable<Integer>() {
    			public  Integer call() {
    				for (int y = 1; y <= limitSqrt; y++) {
    				
    				    int n = (4 * start * start) + (y * y);
    				    if (n <= N && (n % 12 == 1 || n % 12 == 5)) {
    				        isPrime[n] = !isPrime[n];
    				    }
    			
    				    n = (3 * start * start) + (y * y);
    				    if (n <= N && (n % 12 == 7)) {
    				        isPrime[n] = !isPrime[n];
    				    }
    			
    				    n = (3 * start * start) - (y * y);
    				    if (start > y && n <= N && (n % 12 == 11)) {
    				        isPrime[n] = !isPrime[n];
    				    } 
    				} 
    				return 0;
    			}        
    		});
    
        } 
        
        
    	final ExecutorService executorPool = Executors.newFixedThreadPool(4); 
    	try {
    		executorPool.invokeAll(partitions, 10000, TimeUnit.SECONDS);
    		executorPool.shutdown(); 
    	} catch (Exception e) {
    		e.printStackTrace();
    	}
        
    	//BAD
    	while(!executorPool.isTerminated())
    		System.out.println(executorPool.isTerminated());
    	System.out.println(executorPool.isTerminated());
    
    
        for (int n = 5; n <= limitSqrt; n++) {
            if (isPrime[n]) {
                int x = n * n;
                for (int i = x; i <= N; i += x) {
                    isPrime[i] = false;
                } 
            } 
        } 
    
        int count = 0;
        for (int i = 0; i <= N; i++) {
            if (isPrime[i]) 
            	count++;
        }
        long end = System.currentTimeMillis();
        
        System.out.println(count);
    	return end;
    } 
    
    }

  2. #2
    Join Date
    May 2003
    Location
    fdisk
    Age
    37
    Posts
    4,294,966,934
    Thanks
    298
    Thanked 498 Times in 352 Posts

    Default

    I spy the problem. Not going to help you with this tho. You said this is for class so you need to hit the books and or ask your teacher bro. If I or anyone else helps you out with this you wont be learning

  3. #3
    Join Date
    Feb 2010
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default

    I am an idiot for not noticing the obvious race condition

  4. #4
    Join Date
    May 2003
    Location
    fdisk
    Age
    37
    Posts
    4,294,966,934
    Thanks
    298
    Thanked 498 Times in 352 Posts

    Default

    I wish you luck in your classes sir. I always have respect for those who try to further their knowledge. How old are you if you dont mind me asking? U in college or just taking side classes? Whats your major?

  5. The Following User Says Thank You to Asylum For This Useful Post:

    InSaNe (18th January 2013)

Posting Permissions

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