上下文：我正在嘗試使用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也添加一次.
>要計算結果,請執行以下操作：
BigInteger A = product(a);
BigInteger B = prudoct(b);
return a.multiply(a).multiply(b);
要檢視其工作原理,請考慮您的輸入數組為[2,2,2,2,2,3,3,3].是以,有四個2和三個3.數組a和b将分别為
a = [2, 2, 3]
b = [3]
然後,您将遞歸調用以計算這些乘積.請注意,我們将要乘數的數量從7減少到4,幾乎減少了兩倍.這裡的竅門是,對于多次出現的數字,我們隻能計算其中一半的乘積,然後将其乘以2的幂.非常類似于如何在O(log n)時間中計算數字的幂.
标簽：multiplication,biginteger,java,algorithm
來源： https://codeday.me/bug/20191120/2040364.html