与えられた数までのすべての要素の並列階乗計算

Question

私はpi（Chudnovsky公式）を計算する並列プログラムを書く仕事があります。しかし、計算には階乗があります。タスクを分解するために、計算式の計算を開始する前に階乗を計算します（つまり、すべての階乗を計算し、どこかに格納し、読み込む必要があるときに読み込みます）。スポット）。

私はここでいくつかの質問を読んだことがありますが、それらは1つの階乗番号の並列計算に関するものです。これらの数値は、すべての数値を指定されたインデックスまで計算する必要がある場合にはあまり役に立ちません（パラレルsum/productメソッドに基づいています）。誰かがタスクの良い分解のアイデアを持っていますか？

Answer 1

ここでは、forkとjoinの並列処理を使用できます。 10の階乗を計算しなければならないとします。これを行うには2から10までの数を掛けなければなりません。タスクが2または3の乗算になるまで、このタスクを分割できます。ここで

このためのサンプルコードです：これについては

import java.util.ArrayList; 
import java.util.List; 
import java.util.concurrent.ForkJoinPool; 
import java.util.concurrent.RecursiveTask; 

public class ForkTest { 
    public static void main(String[] args) { 
     ForkJoinPool forkJoinPool = new ForkJoinPool(4); 
     for (int i = 2; i < 11; i++) { 
      Factorial myRecursiveAction = new Factorial(2, i); 
      forkJoinPool.invoke(myRecursiveAction); 
      System.out.println("i=" + i + " result=" + myRecursiveAction.getRawResult()); 

     } 
    } 
} 

class Factorial extends RecursiveTask<Long> { 
    private int low; 
    private int high; 

    public Factorial(int low, int high) { 
     this.low = low; 
     this.high = high; 
    } 

    protected Long compute() { 
     if (high - low >= 2) { 
      //System.out.println("Dividing number from : " + low + " - " + high); 
      int mid = (high + low)/2; 
      Factorial lowerRange = new Factorial(low, mid); 
      Factorial higherRange = new Factorial(mid + 1, high); 
      List<Factorial> subtasks = new ArrayList<Factorial>(); 
      subtasks.add(lowerRange); 
      subtasks.add(higherRange); 

      for (Factorial subtask : subtasks) { 
       subtask.fork(); 
      } 

      long result = 1; 
      for (Factorial subtask : subtasks) { 
       result *= subtask.join(); 
      } 
      return result; 

     } else { 
      long facto = low; 
      for (int i = low + 1; i <= high; i++) { 
       facto = facto * i; 
      } 
      //System.out.println("Multiplying number from : " + low + " - " + high + " result=" + facto); 
      return facto; 
     } 
    } 

} 

Answer 2

あなたがダイナミックprogrammigを適用することができます。動的プログラミングは、問題を最も効率的に解決する方法です。実際にはサブ問題を何度も繰り返し計算することは避けています。階乗nについては、常にnを（n-1）倍します！これを適用すると、すべての階乗を計算するためのより速い方法がシリアルであると思います。

BigInteger current = BigInteger.ONE; 
    List<BigInteger> fact = new ArrayList<>(); 
    fact.add(BigInteger.ONE); 
    for (int i = 1; i <= n; i++) { 
     current = current.multiply(BigInteger.valueOf(i)); 
     fact.add(current); 
    }