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

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.

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