我正在Scala（我的選擇）中為在線課程實施Karatsuba 乘法?？紤]到該算法旨在乘以大數，我選擇了BigInt由 Java BigInteger支持的類型。我想有效地實現算法，它使用基數 10 算法從維基百科復制如下：procedure karatsuba(num1, num2) if (num1 < 10) or (num2 < 10) return num1*num2 /* calculates the size of the numbers */ m = max(size_base10(num1), size_base10(num2)) m2 = floor(m/2) /* split the digit sequences in the middle */ high1, low1 = split_at(num1, m2) high2, low2 = split_at(num2, m2) /* 3 calls made to numbers approximately half the size */ z0 = karatsuba(low1, low2) z1 = karatsuba((low1 + high1), (low2 + high2)) z2 = karatsuba(high1, high2) return (z2 * 10 ^ (m2 * 2)) + ((z1 - z2 - z0) * 10 ^ m2) + z0鑒于它BigInteger在內部表示為int[]，如果我可以根據m2進行計算int[]，我可以使用位移來提取數字的低半部分和高半部分。同樣，最后一步也可以通過位移來實現。然而，說起來容易做起來難，因為我似乎無法理解邏輯。例如，如果最大數為999，則二進制表示為1111100111，下半部分為99 = 1100011，上半部分為9 = 1001。我如何獲得上述分割？注意：有一個現有問題顯示了如何在 上使用算術BigInteger而不是位移來實現。因此，我的問題不是重復的。
1 回答
繁星coding
TA貢獻1797條經驗 獲得超4個贊
為了能夠使用位移位進行拆分和重組，基數需要是 2 的冪。使用兩個本身，如鏈接的答案，可能是合理的。然后可以直接用 找到輸入的“長度”，bitLength分割可以實現為：
// x = a + 2^N b
BigInteger b = x.shiftRight(N);
BigInteger a = x.subtract(b.shiftLeft(N));
以位N為單位的大小在哪里a。
鑒于它BigInteger是用 32 位肢體實現的，使用 232 作為基礎是有意義的，確保大移位只涉及整個整數的移動，而不是較慢的代碼路徑，其中BigInteger1 和 31 之間的值移位。這可以通過四舍五入N到 32 的倍數來實現。
這一行中的特定常數，
if (N <= 2000) return x.multiply(y); // optimize this parameter
鑒于該評論，可能不應該太相信。但是對于性能來說應該有一些限制，否則遞歸拆分會過深。例如，當數字的大小為 32 或更少時，只進行乘法顯然更好，但好的截止值可能要高得多。在這個源中BigInteger，截止值用肢體數而不是位數表示，并設置為 80（因此為 2560 位） - 它還有一個其他閾值，高于該閾值它會切換到 3 路 Toom-Cook 乘法唐葉乘法。
添加回答
舉報
0/150
提交
取消