java - 计算 BigInteger[] 的乘积

Question

上下文:我正在尝试使用 Java 中的 BigInteger 类(对于 n>100,000)计算非常大的 n 的阶乘，到目前为止，这是我正在做的事情:

• 使用 Erasthones 筛产生所有小于或等于 n 的素数

• 找出他们将获得哪些权力。

• 将所有数字提高到各自的幂。

• 使用分而治之的递归方法将它们全部相乘。

根据我在互联网上所做的研究，这比简单地将所有 k 乘以 n 快得渐近。但是我注意到，我的实现中最慢的部分是我乘以所有素数幂的部分。我的问题是:

• 有没有更快的方法来计算很多数字的乘积？
• 我的实现是否可以改进？

代码:

public static BigInteger product(BigInteger[] numbers) {
    if (numbers.length == 0)
        throw new ArithmeticException("There is nothing to multiply!");
    if (numbers.length == 1)
        return numbers[0];
    if (numbers.length == 2)
        return numbers[0].multiply(numbers[1]);

    BigInteger[] part1 = new BigInteger[numbers.length / 2];
    BigInteger[] part2 = new BigInteger[numbers.length - numbers.length / 2];
    System.arraycopy(numbers, 0, part1, 0, numbers.length / 2);
    System.arraycopy(numbers, numbers.length / 2, part2, 0, numbers.length - numbers.length / 2);

    return product(part1).multiply(product(part2));
}

• 请注意，BigInteger 使用 karatsuba 算法进行乘法运算。
• 我知道有很多关于计算阶乘的问题。但是我的是关于计算没有太多资源的 BigIntegers 的乘积。 (我看到有人说“使用分而治之的方法”，但我不记得在哪里，也没有看到任何实现。

Answer 1

提高性能的一种方法是执行以下操作:

1. 对需要相乘的数字数组进行排序
2. 创建两个新列表:a 和 b。
3. 对于输入列表中需要相乘的每个数字，它很可能出现不止一次。假设数字 v_i 出现了 n_i 次。然后将 v_i 添加到 a n_i/2 次(向下取整)。如果n_i是奇数，将v_i加一次到b。
4. 要计算结果，请执行以下操作:

BigInteger A = product(a);
BigInteger B = prudoct(b);
return a.multiply(a).multiply(b);

要了解它是如何工作的，假设您的输入数组是 [2, 2, 2, 2, 3, 3, 3]。所以，有四个 2 和三个 3。数组 a 和 b 将相应地成为

a = [2, 2, 3]
b = [3]

然后您将递归调用以计算这些的乘积。请注意，我们将要相乘的数字数量从 7 减少到 4，几乎减少了两倍。这里的诀窍是，对于出现多次的数，我们可以只计算其中一半的乘积，然后计算它的 2 次方。与如何在 O(log n) 时间内计算一个数的幂非常相似。