BigInteger大部分時間優化乘法

您好我想以最及時的優化方式乘以2個大整數。我目前使用karatsuba算法。任何人都可以提出更優化的方法或算法來做到這一點。BigInteger大部分時間優化乘法

感謝

public static BigInteger karatsuba(BigInteger x, BigInteger y) { 

     // cutoff to brute force 
     int N = Math.max(x.bitLength(), y.bitLength()); 
     System.out.println(N); 
     if (N <= 2000) return x.multiply(y);    // optimize this parameter 

     // number of bits divided by 2, rounded up 
     N = (N/2) + (N % 2); 

     // x = a + 2^N b, y = c + 2^N d 
     BigInteger b = x.shiftRight(N); 
     BigInteger a = x.subtract(b.shiftLeft(N)); 
     BigInteger d = y.shiftRight(N); 
     BigInteger c = y.subtract(d.shiftLeft(N)); 

     // compute sub-expressions 
     BigInteger ac = karatsuba(a, c); 
     BigInteger bd = karatsuba(b, d); 
     BigInteger abcd = karatsuba(a.add(b), c.add(d)); 

     return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N)); 
    }

來源

2013-02-23 KingJames

BigInteger.Multiply（）有什麼問題？ – 2013-02-23 08:38:04

它的複雜性是O（n^2）的次序。 Karatsuba約爲O（n^1.5）。我想要一個更優化的。 – KingJames 2013-02-23 08:39:34

如果你想要速度，那爲什麼不嘗試Toom-Cook？ – 2013-02-23 08:48:30

jdk8中的BigInteger版本根據輸入大小在樸素算法，Toom-Cook算法和Karatsuba之間切換，以獲得出色的性能。

來源

2013-11-17 23:17:59

以下是來源，對於好奇者來說：https://github.com/dmlloyd/openjdk/blob/e7f494fc8/jdk/src/java.base/share/classes/java/math/BigInteger.java#L1558 – 2017-10-12 09:03:56

複雜性和實際速度在實踐中是非常不同的事情，因爲參與O符號常量因素。總是有一個複雜的環節，但它可能超出了你所使用的範圍（輸入大小）。算法的實現細節（優化級別）也直接影響這些常數因子。

我的建議是嘗試一些不同的算法，最好來自作者已經花費一些努力優化的庫，並且實際測量並比較它們在輸入上的速度。

關於SPOJ，不要忘記主要問題在別處（即不是大整數的乘法速度）的可能性。

來源

2013-02-23 09:06:35 aditsu

BigInteger大部分時間優化乘法

回答

相關問題