3

並列素因数分解アルゴリズムのアプローチは何か知っている人はいますか?

アルゴリズムのどの段階でスレッドに分割する必要があるのか​​ わかりません..素因数分解を並列に考えるにはどうすればよいですか?

次の 1 つのスレッド コードを検討してください。

    public static void  primeFactorization(ArrayList<Integer> factors, int num){
        //factors is an array to save the factorization elements
        //num is the number to be factorized 
        int limit = num/2+1;

        if(isPrime(num))
            factors.add(num);

        else{
            while(num%2==0){
                factors.add(2);
                num=num/2;
            }

           for (int i=3; i<limit; i+=2){
               while (isPrime(i) && num%i==0){
                   factors.add(i);
                    num = num/i;
               }
           }
       }
    }

    private static boolean isPrime(int x) {
          int top = (int)Math.sqrt(x);
          for (int i = 2; i <= top; i++)
             if ( x % i == 0 )
                return false;
          return true;
    }
4

1 に答える 1

0

これはFork/Join Frameworkの非常に良い使い方のようです。見つけた新しい要素を再帰的に渡すことで、これを使用できるはずです。RecursiveActionも試してみてください。疑似コードでは、次のようなことができるはずです。

public void getFactors(List<Integer> factors, int num){
    if(you can find a factor){
        add the two factors to the pool to be factored further
    }
    else{
        factors.add(num);
    }  
}

補足として、1 から開始するのではなく、中間 (num/2) から開始してそこから行った方が、パフォーマンスが向上する可能性があります。

于 2013-05-08T13:54:52.337 に答える