如何并发Prime分解？

Question

以下代码段计算给定数字的素数因子:

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;
}

计算9223372036854775783的素数因子需要140937ms(这是最后的素数小于Long.MAX_VALUE).有没有办法通过并发实现这种分解,即使用ExecutorService？

编辑:

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;
    }

}

第二编辑:

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;
}

现在代码片段:

    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));

给出输出:

Result: 600851475143
Result: 6857

注意:类名是Factorization,我将方法的名称更改getPrimeFactors为getPrimeFactorsByConcurrentGeneralMethod

Answer 1

呃,在你开始考虑并发实现之前,我建议稍微优化算法.除了2之外,每个素数都是奇数,所以将2作为特殊情况然后从你的循环开始3并将因子增加2.然后代替计算每个循环结束的数量/因子(这也使JIT的优化更加困难我认为)只计算一次Sqrt(N) - 毕竟我们知道每个数字只能有一个素因子> sqrt(N);)

如果你已经这样做了,我会更改你的方法签名,这样你就不会总是从3开始并且达到Sqrt(N)但是给它开始和结束范围.最简单的解决方案是将范围从3-Sqrt(N)分成K个部分,其中K是可用内核的数量(因为使用较小的部分不能真正平衡这些可能会给您带来更好的负载平衡)并将其放入刽子手服务.然后,您只需收集所有结果并从所有较小的列表中创建一个列表.

请注意,这个简单的方法对BigIntegers有更多的作用,因为你总是计算起始编号的值,并且每个除法算法的复杂性在某处取决于bitsize - 如果你使用较小的作业大小并在它们之间进行同步,你也可以解决这个问题.

PS:请注意,您的分割范围算法仍然必须正确处理案例2和sqrt(n).

PPS:我希望你知道这个问题出现在NP中,你只是这样做才能学习并发性.