上下文:我正在尝试使用 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 的乘积。 (我看到有人说“使用分而治之的方法”,但我不记得在哪里,也没有看到任何实现。
最佳答案
提高性能的一种方法是执行以下操作:
- 对需要相乘的数字数组进行排序
- 创建两个新列表:
a
和b
。 - 对于输入列表中需要相乘的每个数字,它很可能出现不止一次。假设数字
v_i
出现了n_i
次。然后将v_i
添加到a
n_i/2
次(向下取整)。如果n_i
是奇数,将v_i
加一次到b
。 - 要计算结果,请执行以下操作:
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)
时间内计算一个数的幂非常相似。
关于java - 计算 BigInteger[] 的乘积,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31570210/