Параллельный факторный расчет ВСЕХ элементов до заданного числа

Question

У меня есть задача написать параллельную программу, которая вычисляет pi (формулу Чудновского). Однако он имеет факториал в расчетах. Поэтому для декомпозиции задачи я хочу рассчитать факториалы, прежде чем я начну вычислять формулу (т. Е. Вычислить все факториалы, где-нибудь их хранить, а затем просто читать, когда их нужно читать, вместо того, чтобы вычислять эти факториалы на место).

Здесь я прочитал несколько вопросов, но они касаются параллельного вычисления одного факториала. Они не очень полезны, когда мне нужно рассчитать ВСЕ числа до определенного индекса (они основаны на методе параллельной суммы/продукта). У кого-нибудь есть идея для хорошего разложения задачи?

Answer 1

Вы можете использовать вилку и присоединиться к параллельной стратегии здесь. Предположим, вам нужно вычислить факторный показатель 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); 
    }