在字符串中實現數字乘法的最快方法（1000000位）

我想爲2個數字乘法編寫最快的算法。每個數字的最大數字都在1000000左右，包含在字符串中。在字符串中實現數字乘法的最快方法（1000000位）

有人想告訴這個問題嗎？我尋找真正的速度解決方案

來源

2010-04-26 Svisstack

如果你想要一個字符串的結果，那麼你將不需要高達1TB的存儲來保存答案？ – philcolbourn 2010-04-26 00:50:48

@philcolbourn該產品只有200萬位;）。 – michalburger1 2010-04-26 01:25:53

@Paul當您將數字與A和B數字相乘時，產品將具有A + B數字，而不是A * B數字。例如，乘以1e10 * 1e10 = 1e20，而不是1e100。 – michalburger1 2010-04-26 09:14:16

您應該將字符串轉換爲數字的二進制表示形式。之後，我知道最快的乘法算法之一是Karatsuba's。

來源

2010-04-26 00:35:04

根據維基百科的文章，Strassen的算法應該勝過Karatsuba從10k到40k數字的數字。 – michalburger1 2010-04-26 01:27:12

只是爲了擴大巴勃羅的答案，假設每個數字是一個字符串1000008十進制數字長。您可以將其轉換爲111112 9位十進制數字，每個都存儲在UInt32中。對這些進行乘法運算。（注意，你將不得不使用UInt64來保存兩個UInt32部分相乘的結果，所以你可能需要一個64位機器。）這應該給你一個基礎10倍的9^2或9^log2（3）加速因子，這取決於算法。

來源

2010-04-26 11:50:01

在字符串中實現數字乘法的最快方法（1000000位）

回答

相關問題