在字符串中实现数字乘法的最快方法（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位）

回答

相关问题