欧拉数并行计算性能未达预期的优化咨询

我正尝试通过公式e=∑(3−4k²/(2k+1)!)（k取值0到10000）计算欧拉数，但使用多线程后未获得理想的性能提升。我尝试将整个求和任务按线程数拆分为若干块，通过提交Future计算各部分和，推测问题可能出在阶乘计算或任务粒度上，调整粒度后仍无明显改善，或许需要其他实现方案。

当前实现代码如下：

ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);
int step = k / numberOfThreads ;
BigDecimal result = BigDecimal.ZERO;
for (int j = 0; j <= k; j += step) {
 Future<BigDecimal> future = executor.submit(new EulerCalculator(j, j + step));
 futures.add(future);
}
for (Future<BigDecimal> future : futures) {
 result = result.add(future.get());
}
public class EulerCalculator implements Callable<BigDecimal> {
 private int start;
 private int end;
 public BigDecimal call() {
  long numerator = 3 - 4 * start * start;
  BigDecimal denominator = factorial(2 * start + 1);
  BigDecimal partialSum = BigDecimal.valueOf(numerator)
  .divide(denominator, 1000, RoundingMode.HALF_EVEN);
  for (int i = start + 1 ; i < end; i++) {
   numerator = 3 - 4 * i * i;
   denominator = denominator.multiply(BigDecimal.valueOf(2 * i * (2*i + 1)));
   partialSum = partialSum.add(BigDecimal.valueOf(numerator)
   .divide(denominator, 1000, RoundingMode.HALF_EVEN));
  }
  return partialSum;
 }
 private BigDecimal factorial(int cur) {
  BigDecimal fact = BigDecimal.ONE;
  for (int i = 2; i <= cur; i++) {
   fact = fact.multiply(BigDecimal.valueOf(i));
  }
  return fact;
}
}

四核处理器上的测试结果：
k=10000
线程数=1：345ms
线程数=2：216ms
线程数=4：184ms
线程数=8：225ms

从你的测试结果和代码来看，性能提升不达预期的核心问题集中在任务划分错误、阶乘计算的冗余与低效、以及BigDecimal大数运算的高开销这几个方面。下面逐个拆解并给出针对性优化方案：

一、修复任务划分的致命错误 #

你的代码中任务划分逻辑存在明显问题：当j循环到k（即10000）时，end = j + step会超出有效范围（比如step=2500时，end=12500），导致最后一个线程计算大量冗余项（k=10001到12500），不仅浪费资源，还造成线程负载严重不均。

正确的划分方式应该将0~10000的10001个项平均分配，确保每个线程的任务范围不超出有效区间：

int totalTerms = k + 1; // 0到10000共10001项
int termsPerThread = (totalTerms + numberOfThreads - 1) / numberOfThreads; // 向上取整保证分配均匀
List<Future<BigDecimal>> futures = new ArrayList<>(numberOfThreads);

for (int t = 0; t < numberOfThreads; t++) {
    int start = t * termsPerThread;
    int end = Math.min(start + termsPerThread, totalTerms) - 1; // 转换为k的最大索引
    if (start > end) break; // 避免最后一个线程无任务
    futures.add(executor.submit(new EulerCalculator(start, end)));
}

同步修改EulerCalculator的逻辑，让它处理start到end（包含）的k值。

二、替换阶乘计算为倒数递推，避免大数运算 #

每个线程开头计算(2*start+1)!是极大的性能浪费：一方面这是天文数字，BigDecimal对超大整数的乘法开销极高；另一方面不同线程之间存在大量重复计算（比如线程1计算到5001!，线程2又要从2开始计算到10001!）。

我们可以利用项与项之间的递推关系彻底规避阶乘计算：
对于第k项：
$$a_k = \frac{3-4k²}{(2k+1)!}$$
第k-1项：
$$a_{k-1} = \frac{3-4(k-1)²}{(2k-1)!}$$
两者的递推关系为：
$$a_k = a_{k-1} \times \frac{3-4k²}{2k \times (2k+1)}$$
初始项$a_0 = \frac{3}{1!} = 3$

基于这个关系，修改后的EulerCalculator可以完全避免超大阶乘计算：

public class EulerCalculator implements Callable<BigDecimal> {
    private final int start;
    private final int end;
    private final BigDecimal prevTerm; // 传递start-1项的值，避免重复递推
    private final int scale = 1000;
    private final RoundingMode roundingMode = RoundingMode.HALF_EVEN;

    public EulerCalculator(int start, int end, BigDecimal prevTerm) {
        this.start = start;
        this.end = end;
        this.prevTerm = prevTerm;
    }

    @Override
    public BigDecimal call() {
        BigDecimal partialSum = BigDecimal.ZERO;
        BigDecimal currentTerm;

        if (start == 0) {
            // 计算初始项a0
            currentTerm = BigDecimal.valueOf(3).divide(BigDecimal.ONE, scale, roundingMode);
            partialSum = partialSum.add(currentTerm);
        } else {
            // 基于前一项递推a_start
            long numerator = 3 - 4 * (long)start * start;
            BigDecimal denominator = BigDecimal.valueOf(2L * start * (2L * start + 1));
            currentTerm = prevTerm.multiply(BigDecimal.valueOf(numerator))
                    .divide(denominator, scale, roundingMode);
            partialSum = partialSum.add(currentTerm);
        }

        // 递推后续项
        for (int i = start + 1; i <= end; i++) {
            long numerator = 3 - 4 * (long)i * i;
            BigDecimal denominator = BigDecimal.valueOf(2L * i * (2L * i + 1));
            currentTerm = currentTerm.multiply(BigDecimal.valueOf(numerator))
                    .divide(denominator, scale, roundingMode);
            partialSum = partialSum.add(currentTerm);
        }

        return partialSum;
    }
}

使用时可以先单线程计算出每个线程起始项的前一项值（比如线程2处理2501~5000，先计算出a2500的值传给它），彻底避免重复递推。

三、预先计算递推前缀，实现线程完全独立 #

如果不想在线程间传递初始项，可以单线程预先计算所有项的倒数阶乘数组，让每个线程直接取用：

// 单线程预先计算所有1/(2k+1)!，开销远小于并行求和
List<BigDecimal> invFactList = new ArrayList<>(totalTerms);
invFactList.add(BigDecimal.ONE); // 1/(1!) = 1
for (int i = 1; i < totalTerms; i++) {
    BigDecimal denominator = BigDecimal.valueOf(2L * i * (2L * i + 1));
    invFactList.add(invFactList.get(i-1).divide(denominator, scale, roundingMode));
}

之后每个线程可以直接通过invFactList.get(k)获取1/(2k+1)!，计算a_k = (3-4k²)*invFactList.get(k)，实现完全独立的并行计算。

四、其他细节优化 #

• 减少BigDecimal对象创建：循环中尽量复用对象，避免频繁创建新实例；
• 用long计算分子：3-4k²用long类型计算，避免不必要的自动装箱；
• 合理设置线程数：四核处理器建议使用4~6个线程，过多线程会增加上下文切换开销（比如你测试中8线程性能下降就是这个原因）。

优化后的预期效果 #

修复任务划分后线程负载会更均衡，替换递推逻辑后BigDecimal运算量会大幅降低，预计4线程耗时可降到100ms以内，接近单线程的3~4倍加速比。

内容的提问来源于stack exchange，提问作者colos_enough