B计划之长乘法讨论
鉴于和liangbch讨论的基选择问题已经很深入了这里开一个帖子讨论下乘法的具体做法
详细的内容近期贴出
打算先写个四路的普通乘法函数
然后考虑分治和高级的情况
NTT不打算考虑
那是另外帖子的任务 因为还没有想好如何具体测试算法，随便说两句
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<<
由目前的资料看，标准的Toom-Cook算法计算的块数应该是在3, 4, 5, 6这四个选择里的，超过6似乎并不能很好的在效率和复杂性上得到平衡，或者说超过6很可能并没有好的算法（纯属猜测，知道的请纠正）。
另外，快速的算法并不是简单的解方程得到系数，而是有预先对应的矩阵的，而且对应阶的矩阵存在很多的，需要在里面选择最小乘法数或者最简单实现的，例如3的最小乘法是5，但最简单实现却需要乘法6个 toom-3算法的实质是将 2个 长为 3L的大数乘法转为为 5次 长为 L的大数乘法。如果转化为6次，则没有实际意义，因为这样复杂度将超过分治法。
toom-3算法的复杂为n^(log_3(5))~~n^1.46497352 ，分治法的复杂度为 n^{log_2(3)}~~ n^{1.5849625}。如果将3L的大数乘法转为为 6次 长为 L的大数乘法的大数乘法，则复杂度为：n^{log_3(6)}~~ n^{1.63093} 你没看我发的几个论文啊
有个中文的说了
5次的存在除以3的操作
6次的仅是加减法
而这个方法并不是迭代方法
所以无所谓什么算法复杂度
和你说的并没关系啊
因为他的乘法是归类到低等的分治运算的
不会再进行Toom-3了 对于大数计算来说，对于长度比较大的L，
多一次L*L（大数乘法）应比多一次(L*L)/3（仅指最后那步大数除以3）耗时要大，
所以分5段应比分6段来得划算，无论算法是否被切换成更低阶的算法。 :)
是啊， 是较大的情况
所以似乎两种情况都需要 对于使用十进制还是二进制，楼主主张使用二进制，这和GMP是一致的。一般说来，在计算远多数输出的情况下，以采用二进制为宜，反之则采用十进制为宜，因为二进制表示输出困难，复杂度较高。
通常认为，多数应用计算占得比重多，输出所占的比重少。但实际应用中，许多应用使用10进制更有优势，象计算有周率，计算e，计算$ \sqrt 2$，$\log 2$等。所以，以计算圆周率作为demo程序的无一例外的使用了基于10进制的表示法。如apfloat,ooura.
我的观点，最好的方案如gxq那样，采用2套算法库，一套是基为2进制，另一套是基为10进制的。
我的计划，目前先实现基为 $ 10^9 $进制的算法，从现在开始，将注意力集中在10进制大数乘法，暂不考虑2进制算法。 :lol
知道
什么叫工业应用
什么叫闹着玩的？
工业应用肯定是二进制库
计算你说的那些都不是工业应用的 有一点可以告诉你，使用2进制的好处大体有2种：
1.需要做大数的位运算，这个其实使用的并不多。
2.二进制具有速度优势，特别是大数乘以单精度整数，但是对于大数乘以大数，二进制的优势其实非常有限，甚至可以忽略。
你我的程序被应用于大规模的工业应用，这种机会太渺茫了，不要好高骛远。
再说了，我也没说放弃2进制库的实现，只是暂时不考虑。 还有就是空间占用
恐怕将来还存在移植问题
10进制移植到64位平台是很困难的
面临改动进制的可能
二进制很可能就改动几个底层汇编就可以了
页:
[1]
2