两个n位数乘法最快的算法是什么？
两个n位数乘法最快的算法是什么？
提问于 2015-02-25 15:43:23
我知道计算机使用移位和加法将两个数字相乘。
位明智的移动乘以并除以二的幂。这个操作比乘法指令更快。一个常数的乘法和一个常数的除法可以使用移位和加减序列来实现。
((x << 2) + x) << 1 // Here 10*x is computed as (x*2^2 + x)*2
(x << 3) + (x << 1) // Here 10*x is computed as x*2^3 + x*2但是，有更快的算法来做到这一点吗？
( Thx寻求帮助:)
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-02-25 15:49:38
编译器使用本机程序集指令的任何组合都是最有效的。
当被常量相乘时，编译器将根据每种策略所需的循环数和二进制代码大小选择直接乘法或移位。这通常是低级别优化器的一项工作，需要对代码运行的处理器有准确的了解。
你不会在这个游戏里打败编译器的。
Stack Overflow用户
发布于 2015-02-25 16:04:38
对于非常大的ns (大约超过1000位数)，有一些专门的算法，它们是：卡拉特赛，图姆-库克，最后是100000位数乘法的怪物：Sch nhage-Strassen。
它们在较小的数字上表现不佳，因为它们的开销很大，但渐近地说，它们比简单的乘法要好得多。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28723246
复制相关文章
相似问题
腾讯云开发者
