Finding prime numbers performance

Question

I am writing an app that finds prime numbers within a specified range. Currently i am updating almost every part of the app and i have also changed the way i find prime numbers. The problem is that the new method seems to be much slower. As a test, the old method takes only 8 seconds to find all the primes from 0 - 100,000. The same task takes the new method between 25 - 30 seconds to complete. I'm not sure why the new method is so much slower. Is there anything i can do to make the new method faster, or at least comparable to the old method, while still keeping the functionality (like the ability to pause it).

Since the code is quite long i have posted links to them as well.

Old Method Full class

public class PrimeFinderThread implements Runnable{
 //Flow control booleans
 public boolean threadRunning = false;
 public boolean scanningNumbers = false;
 public boolean stoppedScanning = true;
 public boolean threadStopped = true;
 //Current number being scanned
 public long currentNumber = 2;
 //Scan progress of current number
 public double currentNumberProgress = 0;
 //List of all found prime numbers
 public List<Long> primeNumbers = new ArrayList<>();
 //Buffer for numbers per second
 public List<Double> numbersPerSecondArray = new ArrayList<>();
 //Times for elapsed time calculation
 public long scanStartTime = 0;
 public long threadStartTime = 0;
 public long pausedTime = 0;
 public long elapsedTime = 0;
 public long lastUpdateTime = 0;
 public long loopStartTime = 0;
 public long loopEndTime = 0;
 public long lastOneSecondUpdateTime;
 //Maximum number to check when scanning for primes
 private double sqrtMax = 0;
 //Numbers scanned per second
 public int numbersPerSecond = 0;
 public int numbersSinceLastSecond = 0;
 //Prime numbers found per second
 public int primesPerSecond = 0;
 public int primesSinceLastSecond = 0;
 @Override
 public void run(){
 while (threadRunning){
 threadStopped = false;
 scanningNumbersLoop: while (scanningNumbers){
 stoppedScanning = false;
 loopStartTime = System.nanoTime();
 currentNumberProgress = 0;
 boolean isPrime = true;
 sqrtMax = Math.round(Math.sqrt(currentNumber));
 for (int i = 2; i <= sqrtMax; i++){
 doUpdates(i);
 //Check if number is prime
 double actualNumber = (double) currentNumber / i;
 double roundedNumber = Math.round(actualNumber);
 //Number is not prime, break out of the loop
 if (actualNumber == roundedNumber){
 isPrime = false;
 break;
 }
 if (!threadRunning | !scanningNumbers){
 break scanningNumbersLoop;
 }
 }
 //Number is prime, add it to the list
 if (isPrime){
 primeNumbers.add(currentNumber);
 primesSinceLastSecond++;
 }
 //Stop thread if end value was reached
 if (currentNumber == ScanForPrimesFragment.endValue){
 scanningNumbers = false;
 currentNumberProgress = 100;
 sendUpdateMessage("endValueReached");
 break;
 }
 //Increase variables
 currentNumber++;
 numbersSinceLastSecond++;
 loopEndTime = System.nanoTime();
 }
 //Thread has stopped scanning for prime numbers
 stoppedScanning = true;
 }
 //Thread has stopped completely
 threadStopped = true;
 }
 /**
 * Called every few milliseconds to update elapsed time and other stats
 * @param i Current iteration of the loop
 */
 private void doUpdates(int i){
 //Update current number progress
 currentNumberProgress = (i / sqrtMax) * 100;
 //Update the time elapsed
 elapsedTime = System.currentTimeMillis() - scanStartTime;
 //Update every second
 if (System.currentTimeMillis() - lastOneSecondUpdateTime >= 1000){
 numbersPerSecond = numbersSinceLastSecond;
 numbersSinceLastSecond = 0;
 primesPerSecond = primesSinceLastSecond;
 primesSinceLastSecond = 0;
 lastOneSecondUpdateTime = System.currentTimeMillis();
 }
 //Update ui
 if (System.currentTimeMillis() - lastUpdateTime >= PrimeNumberFinder.UPDATE_LIMIT_MS){
 lastUpdateTime = System.currentTimeMillis();
 sendUpdateMessage(null);
 }
 }
 /**
 * Send a message to the handler telling the ui to update
 */
 private void sendUpdateMessage(String msgData){
 Message message = ScanForPrimesFragment.handler.obtainMessage();
 Bundle bundle = new Bundle();
 bundle.putString("currentNumber", String.valueOf(currentNumber));
 bundle.putString("msgData", msgData);
 message.setData(bundle);
 ScanForPrimesFragment.handler.sendMessage(message);
 }
}

New Method Full class

public class FindPrimesTask extends Task{
 /**
 * Tag used for logging and debugging.
 */
 private static final String TAG = "FindPrimesTask";
 /**
 * List of all prime numbers found.
 */
 private final List<Long> primeNumbers = new ArrayList<>();
 /**
 * Start and end values. The end value can be modified after the task has started if the user
 * pauses it first. If the end value is set to {@link #LIMIT_NO_LIMIT}, then the task will run
 * forever until stopped by the user or interrupted.
 */
 private final long startValue;
 private long endValue;
 /**
 * If the end value is set to this, then the runnable will run forever until stopped by the
 * user or interrupted.
 */
 public static final int LIMIT_NO_LIMIT = -1;
 /**
 * The current number we are checking.
 */
 private long currentNumber;
 /**
 * The search progress on the current number as a decimal between 0 and 1.
 */
 private float currentProgress = 0;
 private long totalCheckTime;
 private int numbersChecked;
 private final List<EventListener> eventListeners = new ArrayList<>();
 private long[] lastUpdateTimes = new long[2];
 Map<Long, Long> map;
 Map<Long, Long> primesMap;
 /**
 * Create a new {@link FindPrimesTask} to search for prime numbers within a given range.
 *
 * @param startValue The beginning of the search range.
 * @param endValue The end of the search range.
 */
 public FindPrimesTask(final long startValue, final long endValue){
 this.startValue = startValue;
 this.endValue = endValue;
 map = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
 primesMap = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
 }
 @Override
 public void run(){
 //The task has started
 dispatchStarted();
 /**
 * Set the current number to the start value. If the start value is less then 2, then set
 * it to 2 because that is the lowest prime number.
 */
 if (startValue < 3){
 if (endValue >= 2){
 sendOnPrimeFound(2);
 }
 currentNumber = 3;
 }else{
 currentNumber = startValue;
 }
 int sqrtMax;
 boolean isPrime;
 boolean running = true;
 //Loop forever
 while (running){
 //Check if the end value has been reached
 if (endValue == LIMIT_NO_LIMIT || currentNumber <= endValue){
 //Check if the number is divisible by 2
 if (currentNumber % 2 != 0){
 /**
 * Get the square root of the number. We only need to calculate up to the square
 * root to determine if the number is prime. The square root of a long will
 * always fit inside the value range of an int.
 */
 sqrtMax = (int) Math.sqrt(currentNumber);
 //Assume the number is prime
 isPrime = true;
 final long checkStartTime = System.nanoTime();
 /**
 * Check if the number is divisible by every odd number below it's square root.
 */
 for (int i = 3; i <= sqrtMax; i += 2){
 //Check if the number divides perfectly
 if (currentNumber % i == 0){
 isPrime = false;
 break;
 }
 //Calculate current progress
 currentProgress = (float) i / sqrtMax;
 sendOnProgressChanged(currentProgress);
 //Check if we should pause
 tryPause();
 if (shouldStop()){
 running = false;
 break;
 }
 }
 numbersChecked++;
 totalCheckTime += (System.nanoTime() - checkStartTime);
 //Check if the number was prime
 if (isPrime){
 synchronized (LOCK){
 primeNumbers.add(currentNumber);
 //primesMap.put(currentNumber, currentNumber);
 }
 sendOnPrimeFound(currentNumber);
 }
 }
 //Increase currentNumber
 currentNumber++;
 //map.put(currentNumber, currentNumber);
 //Calculate total progress
 if (endValue != LIMIT_NO_LIMIT){
 setProgress((float) (currentNumber - startValue) / (endValue - startValue));
 }
 }else{
 currentNumber = endValue;
 currentProgress = 1f;
 setProgress(1);
 //isRunning = false;
 break;
 }
 }
 dispatchStopped();
 //The task has finished
 if (currentNumber == endValue){
 dispatchFinished();
 }
 }
 public long getAverageCheckTime(){
 return (totalCheckTime - getTotalPauseTime()) / numbersChecked;
 }
 public void setEndValue(long endValue){
 this.endValue = endValue;
 }
 public float getCurrentProgress(){
 return currentProgress;
 }
 public long getCurrentNumber(){
 return currentNumber;
 }
 public long getEndValue(){
 return endValue;
 }
 public long getStartValue(){
 return startValue;
 }
 public long getNumbersPerSecond(){
 return map.size();
 }
 public long getPrimesPerSecond(){
 return primesMap.size();
 }
 public void addEventListener(final EventListener eventListener){
 if (!eventListeners.contains(eventListener)) eventListeners.add(eventListener);
 }
 public interface EventListener{
 void onPrimeFound(final long prime);
 }
 private void sendOnPrimeFound(final long prime){
 for (EventListener eventListener : eventListeners){
 eventListener.onPrimeFound(prime);
 }
 }
}

The new method extends from Task, which is just a simple class extending from Thread

Task Full class

public abstract class Task implements Runnable{
 /**
 * Tag used for logging and debugging.
 */
 private static final String TAG = "Task";
 /**
 * Listeners for task events.
 */
 private final List<TaskListener> taskListeners = new ArrayList<>();
 /**
 * Possible task states.
 */
 public enum State{
 NOT_STARTED,
 RUNNING,
 PAUSED,
 STOPPED,
 FINISHED
 }
 /**
 * Current task state.
 */
 private State state = State.NOT_STARTED;
 /**
 * Total task progress. If ongoing task, progress will remain at 0.
 */
 private float progress = 0f;
 /**
 * Keep track of when the task was started and paused. These values are also used to calculate
 * the elapsed time.
 */
 private long startTime;
 private long lastPauseTime;
 private long totalPauseTime;
 /**
 * Lock used to pause the current thread when the task is paused.
 */
 protected final Object LOCK = new Object();
 private boolean requestPause = false;
 private boolean requestStop = false;
 //Override methods
 @Override
 public abstract void run();
 //Utility methods
 protected void tryPause(){
 if (requestPause){
 synchronized (LOCK){
 try{
 //Pause
 dispatchPaused();
 Log.e(TAG, "Time elapsed pause: " + getTimeElapsed());
 sendOnTaskPaused();
 //Wait until notified to resume
 LOCK.wait();
 //Resume
 dispatchResumed();
 }catch (InterruptedException e){
 if (PrimeNumberFinder.DEBUG)
 Log.e(TAG, "Task was interrupted while paused!");
 }
 }
 }
 }
 protected boolean shouldStop(){
 return requestStop;
 }
 //Lifecycle methods
 public void start(){
 run();
 }
 protected void dispatchStarted(){
 this.startTime = System.currentTimeMillis();
 setState(State.RUNNING);
 sendOnTaskStarted();
 }
 public void pause(){
 requestPause = true;
 }
 private void dispatchPaused(){
 requestPause = false;
 lastPauseTime = System.currentTimeMillis();
 setState(State.PAUSED);
 }
 public void resume(){
 synchronized (LOCK){
 LOCK.notify();
 }
 }
 private void dispatchResumed(){
 totalPauseTime += (System.currentTimeMillis() - lastPauseTime);
 setState(State.RUNNING);
 sendOnTaskResumed();
 }
 protected void dispatchStopped(){
 setState(State.STOPPED);
 }
 protected void dispatchFinished(){
 setState(State.FINISHED);
 }
 public void stop(){
 requestStop = true;
 }
 //Getters and setters
 public void addTaskListener(final TaskListener taskListener){
 if (!taskListeners.contains(taskListener)) taskListeners.add(taskListener);
 }
 public long getTimeElapsed(){
 if (startTime == 0){
 return 0;
 }
 return System.currentTimeMillis() - startTime - totalPauseTime;
 }
 public float getProgress(){
 return progress;
 }
 public void setProgress(float progress){
 this.progress = progress;
 }
 public State getState(){
 return state;
 }
 private void setState(State state){
 this.state = state;
 switch (state){
 case PAUSED:
 sendOnTaskPaused();
 break;
 case STOPPED:
 sendOnTaskStopped();
 break;
 case FINISHED:
 sendOnTaskFinished();
 break;
 }
 }
 protected long getTotalPauseTime(){
 return totalPauseTime;
 }
 //Callbacks
 private void sendOnTaskStopped(){
 for (TaskListener taskListener : taskListeners){
 taskListener.onTaskStopped();
 }
 }
 private void sendOnTaskStarted(){
 for (TaskListener taskListener : taskListeners){
 taskListener.onTaskStarted();
 }
 }
 private void sendOnTaskPaused(){
 for (TaskListener taskListener : taskListeners){
 taskListener.onTaskPaused();
 }
 }
 private void sendOnTaskResumed(){
 for (TaskListener taskListener : taskListeners){
 taskListener.onTaskResumed();
 }
 }
 private void sendOnTaskFinished(){
 for (TaskListener taskListener : taskListeners){
 taskListener.onTaskFinished();
 }
 }
 protected void sendOnProgressChanged(final float percent){
 for (TaskListener taskListener : taskListeners){
 taskListener.onProgressChanged(percent);
 }
 }
}

• Ryan Mills: You have not included sufficent information to compile and run you code. First, show your imports: import java.util.ArrayList;, import java.util.List; etc. Then, make sure all dependencies are included. For example, what is ScanForPrimesFragment? Where is it defined?
• rossum: You do not appear to be using the sieve of Eratosthenes. That will run a lot faster than your current method - dividing by odd number. A sieve will allow you to divide only by prime numbers, omitting 9, 15, 21 25 etc.
• mtj: Also not an answer to your question, but a "+1" to rossums comment: just to get a feeling for the time needed, I hacked together a sieve of erastosthenes to calculate the prime numbers from 0 to 100000 and came to a runtime of 3 ms (modern hardware, single threaded). Extending this to a million goes up to 13 ms on my system. Thus, whatever you do, your algorithm seems to be so sub-par, that following through with it is probably not worthwile.
• TychoTheTaco: My tests were all run on an android device in a single thread, so i wasn't expecting great performance. However i was able to bring the time down to about 2 seconds (for 100,000). I have also tested this code on my PC (i7-4990 @ 3.6Ghz) and it took 20ms to get to 100,000 and about 280ms to get to 1 mil (again on a single thread). In the code I posted above, i found that sendOnProgressChanged() was taking a relatively long time, considering it is called every iteration. Removing that helped the performance, but I think i might take your suggestion and implement the sieve. Thanks for the help!

Answer 1

I am taking a step back and writing in general answer to address your concerns.

I think you are doing good stuff but your code looks so much complex because you have combined 3 things together.

1) Finding prime numbers

2) Implement multi threaded application

3) Profile application performance

I would suggest to make implementation of these 3 component separate from each other. Make your design modular so that you can address issues at each level.

As already mentioned in comments, Eratosthenes algorithm is most efficient in terms of solving problem-1

For profiling, there are few good open source tools available which you can use in order to compare performance between different implementation of your application.

Some tools are discussed here: https://stackoverflow.com/questions/948549/open-source-java-profilers

• TychoTheTaco: I have changed my implementation quite a bit now, to allow these 3 criteria to be met and i am satisfied with it. Thanks for the tips.