Karatsuba乘法的基本情況

Question

想知道爲什麼Karatsuba乘法的基本情況（這裏顯示：http://www.sanfoundry.com/java-program-karatsuba-multiplication-algorithm/）被選爲「N < = 10」？我發現「N < = 4,3,2,1」不會給我一個正確的結果。任何人都能解釋？

Answer 1

Karatsuba的算法可以正確處理任何「足夠大」的基本情況，其中「足夠大」的意思是「足夠大，當它被分成更小的子問題時，那些子問題確實更小並且產生正確答案。從這個意義上說，Karatsuba並不存在「基礎」案例，而是基本案例的基本案例。

老實說，你鏈接的代碼似乎並不像它是一個非常合理的算法實現。它與long s一起工作，在任何合理的系統上它已經可以在O（1）時間內相乘，並且它們的基本情況是當數字小於10時停止，這意味着對於64位數的遞歸總是在一步之後終止。更好的實現可能會使用類似BigInteger類型的類型，它可以支持任意精度乘法。此時，選擇最佳基本情況是性能調整的問題。使基本情況下的數字數量太小，處理較小數字的遞歸將花費更多的時間，而不僅僅是做一個天真的乘法。讓基數過高，你會開始看到放緩，因爲遞歸步驟更好地處理了情況，而不是使用簡單乘法的花費。

Answer 2

具有小於10位數的數字可以原生地相乘（x*y），因爲結果總是適合於有符號的64位整數。

雖然使用long數據類型沒有多大意義，因爲大多數不會溢出的數字組合只會在本機進行評估。您必須更改爲BitInteger或類似的東西，並使用更大的數字從算法中獲得任何收益。

至於爲什麼它沒有達到N的下限，我不確定。該算法必須能夠將兩個數字分成兩個相似大小的部分。我想在某些情況下，它會以零或負數結束。

Answer 3

如果你在你的文章中包含了源代碼，你很可能會很快得到一個點對點的答案。
如果你使用類似BigInteger.divideAndRemainder(dividend, divisor)到「拆分」你的號碼，你就不會跑的風險，像

long d = y/m; 
long c = y - (d * N); 

（使用除數不同的乘數）代碼的東西。
請注意，兩個10數字的乘積並不總是適合於Java的long。