How to Concurrent Prime Factorization?

Question

The following code snippet calculate prime factors of a given number:

public static LinkedList<Long> getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    for (Long factor = Long.valueOf(2); factor <= number / factor; factor++) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

It takes 140937ms to calculate prime factors of 9223372036854775783 (it is a last prime less than Long.MAX_VALUE). Is there any way to implement this factorization by concurrency i.e., by using ExecutorService?

Edit:

public static void getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number) + 1;

    ExecutorService service = Executors.newFixedThreadPool(2);
    LinkedList<Future<LinkedList<Long>>> futures = new LinkedList<Future<LinkedList<Long>>>();
    futures.add(service.submit(new PrimeFactor(3, limit / 2, number)));
    futures.add(service.submit(new PrimeFactor(1 + limit / 2, limit, number)));

    for (Future<LinkedList<Long>> future : futures) {
        try {
            primeFactors.addAll(future.get());
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
    service.shutdown();

    if(number>1) {
        primeFactors.add(number);           
    }

    System.out.println(primeFactors);
}

private static class PrimeFactor implements Callable<LinkedList<Long>> {
    private long lowerLimit;
    private long upperLimit;
    private Long number;

    public PrimeFactor(long lowerLimit, long upperLimit, Long number) {
        this.lowerLimit = lowerLimit;
        this.upperLimit = upperLimit;
        this.number = number;
    }

    public LinkedList<Long> call() throws Exception {
        LinkedList<Long> primeFactors = new LinkedList<Long>();
        for (long i = lowerLimit; i < upperLimit; i += 2) {
            if (number % i == 0) {
                primeFactors.add(i);
                while (number % 2 == 0) {
                    number /= i;
                }
            }
        }
        return primeFactors;
    }

}

2nd Edit:

public static LinkedList<Long> getPrimeFactorsByFastGeneralMethod(long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number);

    for (long factor = 3; factor <= limit; factor += 2) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {
                number /= factor;
            }
        }
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

Now code snippet:

    LinkedList<Long> primeFactors = Factorization.getPrimeFactorsByConcurrentGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

    primeFactors = Factorization.getPrimeFactorsByFastGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

is giving the output:

Result: 600851475143
Result: 6857

Note: The class name is Factorization and I changed the name of the method getPrimeFactors to getPrimeFactorsByConcurrentGeneralMethod

Billy

The first obvious improvement would be to replace the Long variables by long ones. This reduces the overhead of boxing and unboxing the wrapper objects. – Reinwald

@Christian Semrau primarily I wrote this one using BigInteger in place of Long. – Billy

Answer 1

Uh before you start thinking about concurrent implementations, I'd propose optimizing the algorithm a bit. Apart from 2 every prime is odd, so make 2 a special case and then start at 3 with your loop and increase the factor by 2. Then instead of computing number / factor every loop ending (that also makes optimizing for the JIT harder I think) just compute Sqrt(N) once - after all we know that every number can have only one prime factor > sqrt(N) ;)

If you've done that I'd change your method signature so that you don't always start at 3 and work up to Sqrt(N) but give it start and end ranges. The simplest solution would be to split the range from 3-Sqrt(N) into K parts where K is the number of cores available (since this is not really balanced using smaller parts may give you a better load balancing) and throw that into an executioner service. You then just have to gather all results and create one list from all the smaller lists.

Just note that this simple approach does more work for BigIntegers since you always compute the values on the start number and every division algorithm's complexity somewhere depends on the bitsize - you can solve that as well if you eg use smaller job sizes and synchronize between those.

PS: Note that your split range algorithm still has to handle the case 2 and sqrt(n) correctly.

PPS: And I hope you're aware that this problem is in NP and you're only doing this to learn a bit about concurrency.

Overdue

@Overdue I have added a modified version as you instructed. Are you talking about this? Is it okay? I passed 2*101*329569479697L as parameter and it is printing [2, 101, 33286517449397]. But I have some trouble to split the range into K where k=number_of_core. Can you show me how can I do it? Thanks. It takes 14188ms to factorize a prime 9223372036854775783L. – Billy

Yep that looks fine. Using an inclusive lower and exclusive upper range is good too (makes all computations much simpler). To get your k just use Runtime.getRuntime().availableProcessors(); and then just use a simple loop. Note that as nulldevice says there are more complex algorithms out there than the simple brute force approach, but it's a nice way to play a bit with concurrency (now you could look how long each split takes to execute - I'm pretty sure that won't be balanced, so try something about that eg)# – Overdue

@Overdue I am very sorry. I think I made some mistake. I wrote them into my original post. – Billy

Not much time for a thorough look to see if there's a more general problem, but there's a "while (number % 2 == 0)" in your call statement which should obviously be number % i – Overdue

Furthermore your (number > 1) check won't work for obvious reasons as well – Overdue

@Overdue yes you are right. Your last two suggestions worked very well. – Billy

Answer 2

No, there are no such easy method, at least known one. The problem of optimal integer factorization is still open in math.

You could use an Elliptic Curve Method (ECM) Prime Factorization. It is suited well for a parallel computation. But the method itself is not trivial - several thousands lines of code. Sources are available for example here

Quartziferous

Answer 3

You could tweak your implementation in some ways:

1. Avoid unnecessary autoboxing as Christian Semrau already mentioned in his comment.
2. Create a shortcut for the "simple" case, e. g. you iterate over every number between 2 and number/2. This is unnecessary since 2 is the only even prime factor. You will save half of the number of iterations with this shortcut in the best case.
3. You don't need to calculate the prime factors of number, sqrt(number) is sufficient.

4. There are more efficient ways to Integer factorization

   public static List<Long> getPrimeFactors(long number) {
       List<Long> primeFactors = new ArrayList<Long>();
   
       // Only process natural numbers
       if(number < 1l) {
           return primeFactors;
       }
   
       // The only prime factor of 1 is 1
       if(number == 1l) {
           primeFactors.add(1l);
           return primeFactors;
       }
   
       // Even have the prime factor 2
       if(number % 2l == 0l) {
           primeFactors.add(2l);
   
           while(number % 2l == 0l) {
               number /= 2l;
           }
       }
   
       // Iterate from 3 to sqrt(number) to calculate the remaining prime factors
       for (long factor = 3l; factor < Math.sqrt(number); factor+=2l) {
           if (number % factor == 0) {
               primeFactors.add(factor);
               while (number % factor == 0) {                  
                   number /= factor;
               }
           }           
       }
   
       if (number > 1) {
           primeFactors.add(number);
       }
   
       return primeFactors;
   }
   

Transposition