Karatsuba乘法改進

-1

我實施了Karatsuba乘法算法來達到我的教育目標。現在我正在尋找更多的改進。我已經實現了某種長算術，並且它能夠很好地工作，不管我使用的整數表示的基數是否超過。含底座和範圍[10^50000, 10^50001]與clang++ -O3乘兩個隨機整數編譯需要：Karatsuba乘法改進

Naive algorithm took me 1967 cycles (1.967 seconds) 
Karatsuba algorithm took me 400 cycles (0.4 seconds)

而基礎相同的數字：

Naive algorithm took me 409 cycles (0.409 seconds) 
Karatsuba algorithm took me 140 cycles (0.14 seconds)

是否有改善的方法這個結果？現在我使用這些函數來完成我的結果：

void finalize(vector<int>& res) { 
    for (int i = 0; i < res.size(); ++i) { 
     res[i + 1] += res[i]/base; 
     res[i] %= base; 
    } 
}

正如你可以看到它進行計算，並把它推到下一個數字的每一步。如果我以>=1000爲基數，結果將會溢出。

如果您在我的代碼中看到我使用int向量來表示長整數。根據我的基數，一個數字將分成不同的部分。現在我看到幾個選項：

使用long long類型載體，但它可能也將被溢出了廣大長度整數
實現長期算術

隨身攜帶的表示我參觀過之後我決定擴大這個問題。假設我們想要將我們的長整數表示爲一個整數的向量。對於instanse：

ULLONG_MAX = 18446744073709551615

而對於輸入我們通過第210號Fibonacci數34507973060837282187130139035400899082304280不適合任何類型stadard。如果我們在基礎千萬爲int的矢量代表它就會像：

v[0]: 2304280 
v[1]: 89908 
v[2]: 1390354 
v[3]: 2187130 
v[4]: 6083728 
v[5]: 5079730 
v[6]: 34

當我們做乘法，我們可能會（爲簡單起見，讓它成爲兩個相同的數字） (34507973060837282187130139035400899082304280)^2：

v[0] * v[0] = 5309706318400 
... 
v[0] * v[4] = 14018612755840 
...

這只是第一行，我們必須做這六個步驟。當然，某些步驟會在乘法或進位計算後引起溢出。

如果我錯過了什麼，請告訴我，我會改變它。如果你想看到完整的版本，它是我的github

來源

2015-07-10 vpetrigo

如果你有工作代碼，那麼也許你的問題更適合http://codereview.stackexchange.com/？ – EdChum

我投票結束這個問題作爲題外話，因爲它屬於codereview。在那裏，你需要在你的帖子中發佈代碼，而不是鏈接到你的github。你只需要發佈相關的部分。 – UmNyobe

如果你真的想加速，那麼你應該使用另一種更快的算法：例如Toom-Cook或者傅立葉變換。 –

基地2^64和基地2^32是做高精度運算最受歡迎的基地。通常，這些數字存儲在未簽名的整型中，因爲它們在溢出方面具有良好的語義。

例如，一種可以從除了檢測進位，如下所示：

uint64_t x, y; // initialize somehow 
uint64_t sum = x + y; 
uint64_t carry = sum < x; // 1 if true, 0 if false

另外，彙編語言通常具有幾個指令「進位加」;如果您可以編寫內聯彙編（或者可以訪問內部函數），則可以利用這些優勢。對於乘法，大多數計算機具有可以計算一個機器字 - >兩個機器字產品的機器指令;有時候，獲得兩半的指令稱爲「乘法hi」和「乘法低」。您需要編寫程序集來獲取它們，儘管許多編譯器提供了更大的整數類型，這些整數類型的使用可以讓您訪問這些指令：在gcc可以實現多重喜爲

uint64_t mulhi(uint64_t x, uint64_t y) 
{ 
    return ((__uint128_t) x * y) >> 64; 
}

當人們無法利用這一點，他們在做2^32而是乘法，使他們能夠使用相同的方法來實現便攜式mulhi指令，使用uint64_t作爲雙數字類型。

如果你想編寫高效的代碼，你真的需要利用這些更大的乘法指令。基數2^32中的數字乘以比基數10中的數字乘以功能強九十倍以上。基數2^64中的數字乘以4倍。而且你的計算機可能比你在10次乘法中實現的更快。

來源

2015-07-10 10:28:18 Hurkyl

但正如我說我使用基於整數的向量長算術represend龐大的數字作爲擁有超過20位甚至普通'uint64_t'類型不適合整。 – vpetrigo

@vpetrigo：但是'2^64'中的一個* 2 *位數字可以存儲一個20位十進制數的數字。 – Hurkyl

Karatsuba乘法改進

回答

相關問題