Counting multiples of 3 or 5 using threads

Question

I have a modified version of the first Project Euler problem — where I find the sum of all the numbers below the value 2100000000 that are multiples of 3 or 5 using a multi-threaded program.

The concept of the partially-multi-threaded version: we have a value sum, where we add together all the multiples of 3 (that are not multiples of 3 and 5). Then, we add all the multiples of 5 (that were multiples of 3 and 5) to sum.

On my computer, this code executes at (an average) 4050 milliseconds. How can the execution time be reduced?

MultipleOf3.java

//Calculates the sum of multiples of 3 from 3 to 2100000000.
public class MultipleOf3  implements Runnable {
    private volatile int sum = 0;

    public void run() {
        int counter = 1;
        for(int i = 3; i < 2100000000; i += 3) {

          //If the multiple of 3 ends with a 5 or 0, then skip it because
           // it is a multiple of 5.
          if(counter == 5) {
                counter = 1;
                continue;
           }

           sum += i;
           counter++;
        }
    }

   public int getSum() {
       return sum;
   }
}

MultipleOf5.java

// Calculates the sum of multiples of 5 from 5 to 2100000000.

    public class MultipleOf5  implements Runnable {
         private volatile int sum = 0;

         public void run() {
              //This time we added all multiples of 5 - including the 
             //values that were skipped that were multiples of 3 and 5
             for(int i = 5; i < 2100000000; i += 5) {
                sum += i;
             }
         }

         public int getSum() {
             return sum;
         }

    }

Main.java

public class Main {

    private static int parallelSolution() throws InterruptedException{
        int totalSum = 0;

        MultipleOf3 multipleOf3 = new MultipleOf3();
        Thread newThread = new Thread(multipleOf3);

        MultipleOf5 multipleOf5 = new MultipleOf5();
        Thread secondThread = new Thread(multipleOf5);

        newThread.start();
        secondThread.start();

        newThread.join();
        secondThread.join();

        totalSum += multipleOf3.getSum();
        totalSum += multipleOf5.getSum();

         return totalSum;
   }


    public static void main(String[] args) throws InterruptedException  {
        long startTime = System.currentTimeMillis();    
        int sum = parallelSolution();   
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;

        System.out.println("The total sum = " + sum);
        System.out.println("Elapsed time is " + elapsedTime);
    }

}

Answer 1

Bug

Both sums are much too large to fit into a 32-bit int. So this code returns an incorrect answer.

Gaussian solution

If you first calculate how many multiples of whatever there are, you can use the Gaussian formula to get the sum directly.

public class MultipleOf implements Runnable {

    private final int interval;
    private final long ceiling;
    private long sum;

    public MultipleOf(int interval, long ceiling) {
        this.interval = interval;
        this.ceiling = ceiling;
    }

    @Override
    public void run() {
        // n is the number of multiples of interval that are less than ceiling
        long n = (ceiling - 1) / interval;
        sum = interval * (n * (n+1) / 2);
    }

    public long getSum() {
        return sum;
    }

}

This also requires only one multiples class and removes the magic numbers from the class.

You can run the code like

    private static long parallelSolution(long ceiling) throws InterruptedException {
        long totalSum = 0;

        MultipleOf multipleOf3 = new MultipleOf(3, ceiling);
        Thread thread3 = new Thread(multipleOf3);

        MultipleOf multipleOf5 = new MultipleOf(5, ceiling);
        Thread thread5 = new Thread(multipleOf5);

        MultipleOf multipleOf15 = new MultipleOf(15, ceiling);
        Thread thread15 = new Thread(multipleOf15);

        thread3.start();
        thread5.start();
        thread15.start();

        thread3.join();
        thread5.join();
        thread15.join();

        totalSum += multipleOf3.getSum();
        totalSum -= multipleOf15.getSum();
        totalSum += multipleOf5.getSum();

         return totalSum;
    }

When I ran this with almost your original main, I got an answer in 2 milliseconds. Your original code ran in 6000 milliseconds in my test. Of course, running without threads takes 0 milliseconds.

I also changed the thread names to be more descriptive.

Overhead

I'd try running your solution without threads and see if it is faster or slower.

Answer 2

Using a volatile class member in your MultipleOf?? classes is overkill and will result in an unnecessary performance hit. The way that you have constructed the classes, you only use the variable from a single thread at a time. The writer thread updates the variable as it is working out the multiples, however the you are joining the thread before you read the value from your main thread. This means that you don't need the protection of volatile.

Changing the class member to a normal int has a significant impact on my system (time reduces from 10 seconds down to 3.5 seconds for the partially threaded implementation).

This can further be increased by using a local variable for the counting, rather than a class member, then assigning the class member afterwards. This reduces the time on my system further down to less than a second.

public class MultipleOf3  implements Runnable {
    private   int sum = 0;

    public void run() {
        int counter = 1;
        int summer=0;
        for(int i = 3; i < 2100000000; i += 3) {

          //If the multiple of 3 ends with a 5 or 0, then skip it because
           // it is a multiple of 5.
          if(counter == 5) {
                counter = 1;
                continue;
           }

           summer += i;
           counter++;
        }
        sum = summer;
    }

   public int getSum() {
       return sum;
   }
}