5

次のコード スニペットは、指定された数値の素因数を計算します。

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

}

2回目の編集:

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

4

3 に答える 3

6

並列実装について考える前に、アルゴリズムを少し最適化することを提案します。2 を除いてすべての素数は奇数なので、2 を特別なケースにしてから、ループで 3 から開始し、係数を 2 ずつ増やします。次に、ループの終わりごとに数/係数を計算する代わりに (これにより、JIT の最適化も難しくなると思います) ) Sqrt(N) を 1 回計算するだけです - 結局のところ、すべての数値は素因数 > sqrt(N) を 1 つしか持てないことがわかっています ;)

あなたがそれをしたら、私はあなたのメソッドの署名を変更して、あなたがいつも3から始めてSqrt(N)まで働くのではなく、開始と終了の範囲を与えるようにします。最も簡単な解決策は、範囲を 3-Sqrt(N) から K 個のパーツに分割することです。ここで、K は利用可能なコアの数です (これは実際にはバランスが取れていないため、小さいパーツを使用すると負荷分散が向上する可能性があります)。処刑人サービス。次に、すべての結果を収集し、すべての小さいリストから 1 つのリストを作成するだけです。

常に開始番号の値を計算し、すべての除算アルゴリズムの複雑さはどこかでビットサイズに依存するため、この単純なアプローチは BigInteger に対してより多くの作業を行うことに注意してください。たとえば、より小さいジョブサイズを使用してそれらの間で同期する場合も同様に解決できます。

PS: 分割範囲アルゴリズムは、ケース 2 と sqrt(n) を正しく処理する必要があることに注意してください。

PPS: そして、この問題は NP にあり、並行性について少し学ぶためにこれを行っているだけであることを認識していただければ幸いです。

于 2011-06-26T13:52:45.643 に答える
1

いいえ、そのような簡単な方法はありません。少なくとも既知の方法はあります。最適な整数因数分解の問題は、数学ではまだ未解決です。

Elliptic Curve Method (ECM) Prime Factorizationを使用できます。並列計算に適しています。しかし、メソッド自体は簡単ではありません - 数千行のコードです。ソースは、たとえばここで入手できます

于 2011-06-26T14:48:51.773 に答える
0

いくつかの方法で実装を微調整できます。

  1. Christian Semrau がコメントで既に述べたように、不要なオートボクシングは避けてください。
  2. 「単純な」ケースのショートカットを作成します。たとえば、2 と number/2 の間のすべての数値を反復処理します。偶数の素因数は 2 だけなので、これは不要です。最良の場合でも、このショートカットを使用すると反復回数の半分を節約できます。
  3. の素因数を計算する必要はありません。numberでsqrt(number)十分です。

  4. 整数因数分解にはもっと効率的な方法があります

    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;
}
于 2011-06-26T14:09:22.330 に答える