字節數組Karatsuba乘法優化

Question

我已經實現了兩個字節數組的乘法，它工作正常。更確切地說，我需要將一個64字節的操作數與一個32字節的操作數相乘。

我實現了它最簡單的方法：我做了一個雙循環，並計算每個數組中每個字節的產品。 因此，對於具體的值，它需要64 * 32 = 2048步驟。

我試圖用Karatsuba方法對其進行優化。 所以我按照以下方式進行：

a的長度爲64字節，而b的長度爲32字節。 a = p * 16^(32) + q（所以p和q兼得的32個字節的長度）和計算：a * b = p * b * 16^(32) + q * b（與之前描述了我的函數的產品計算）

我們在分裂a。

我得到正確的結果，但它需要相同的時間來計算：兩個32字節數組的乘法：32 * 32 * 2 = 64 * 32 = 2048。

我的問題是以下內容：使用Karatsuba優化我的乘法，我應該完全遞歸編程嗎？以其他方式永遠不會更快？

謝謝您提前:) :)

Answer 1

是的，Karatsuba算法是只有在遞歸執行時纔有效。但記住：Karatsuba是並不總是比簡單算法更快，這需要O(n^2)（通常我們假設兩個數字具有相同的長度，如果我們要乘以大數）。對於小輸入（也可以是1，也可以是15，這取決於你的CPU）的簡單算法可以更快，所以Karatsuba的最佳使用方法是：

1. 如果size > MIN_SIZE_FOR_KARATSUBA（你必須通過實驗找到它） ，然後做分割並遞歸調用Karatsuba。
2. 如果size <= MIN_SIZE_FOR_KARATSUBA，那麼只需乘以簡單的算法。

而且也，你的陣列不拆成字節乘法，他們整數存儲在基地1000或類似的東西，因爲你很容易溢出的類型。

Karatsuba算法的最佳實現描述in this link。通常Karatsuba需要O(n log n)內存，但這裏有一些技巧，它只需要O(n)內存。

如果您不想多次使用函數調用（因爲函數調用是編程中最慢的操作），那麼您可以使用循環並自己實現堆棧，如my implementation中所述。

Answer 2

哇！我作爲程序員的第一份工作之一就是優化了COBOL運行時系統的乘法算法 - 這是31年前的事情。

我認爲您會發現有效的技術是將字節組合成更大的單位。那時，只有32位是可用的，所以兩個字節被合併成一個短路，並且短路成倍增加到32位整數。但在Java中你有64位可用，所以你可以乘以兩個整數得到一個長整數。

所以，你應該使一個陣列的16個整數A1以及通過將字節B中的陣列B1 8整數。例如。有時是這樣的：

a1[0] = (a[0] << 24) + (a[1] << 16) + (a[2] << 8) + a[3] 

或者你可以寫一個循環來更簡明地做到這一點。

然後乘以a1和b1，這應該採取128個操作。

我會擔心溢出和簽名與無符號值。最高位後面的數字應該是無符號的，但Java沒有無符號修飾符。但是，在Java 8中，對未簽名操作有一些支持：請參閱Primitive Data Types。

如果你不能讓ints/longs無符號地工作，你總是可以將2或3個字節組合成整數並浪費一些最高位來爲符號位提供空間。