我实施了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
如果你有工作代码,那么也许你的问题更适合http://codereview.stackexchange.com/? – EdChum
我投票结束这个问题作为题外话,因为它属于codereview。在那里,你需要在你的帖子中发布代码,而不是链接到你的github。你只需要发布相关的部分。 – UmNyobe
如果你真的想加速,那么你应该使用另一种更快的算法:例如Toom-Cook或者傅立叶变换。 –