B计划之长乘法讨论

无心人

鉴于和liangbch讨论的基选择问题已经很深入了 这里开一个帖子讨论下乘法的具体做法 详细的内容近期贴出 打算先写个四路的普通乘法函数 然后考虑分治和高级的情况 NTT不打算考虑 那是另外帖子的任务

无心人

因为还没有想好如何具体测试算法，随便说两句 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>><<<<<<<<<<<<<<<<<<<<<<<<<<<< 由目前的资料看，标准的Toom-Cook算法计算的块数应该是在3, 4, 5, 6这四个选择里的，超过6似乎并不能很好的在效率和复杂性上得到平衡，或者说超过6很可能并没有好的算法（纯属猜测，知道的请纠正）。 另外，快速的算法并不是简单的解方程得到系数，而是有预先对应的矩阵的，而且对应阶的矩阵存在很多的，需要在里面选择最小乘法数或者最简单实现的，例如3的最小乘法是5，但最简单实现却需要乘法6个

liangbch

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了

gxqcn

对于大数计算来说，对于长度比较大的L， 多一次L*L（大数乘法）应比多一次(L*L)/3（仅指最后那步大数除以3）耗时要大， 所以分5段应比分6段来得划算，无论算法是否被切换成更低阶的算法。

无心人

是啊， 是较大的情况 所以似乎两种情况都需要

liangbch

　对于使用十进制还是二进制，楼主主张使用二进制，这和GMP是一致的。一般说来，在计算远多数输出的情况下，以采用二进制为宜，反之则采用十进制为宜，因为二进制表示输出困难，复杂度较高。 　 通常认为，多数应用计算占得比重多，输出所占的比重少。但实际应用中，许多应用使用10进制更有优势，象计算有周率，计算e，计算$ \sqrt 2$，$\log 2$等。所以，以计算圆周率作为demo程序的无一例外的使用了基于10进制的表示法。如apfloat,ooura. 　我的观点，最好的方案如gxq那样，采用2套算法库，一套是基为2进制，另一套是基为10进制的。 　我的计划，目前先实现基为 $ 10^9 $进制的算法，从现在开始，将注意力集中在10进制大数乘法，暂不考虑2进制算法。

无心人

知道 什么叫工业应用 什么叫闹着玩的？ 工业应用肯定是二进制库 计算你说的那些都不是工业应用的

liangbch

有一点可以告诉你，使用2进制的好处大体有2种： 1.需要做大数的位运算，这个其实使用的并不多。 　　2.二进制具有速度优势，特别是大数乘以单精度整数，但是对于大数乘以大数，二进制的优势其实非常有限，甚至可以忽略。 你我的程序被应用于大规模的工业应用，这种机会太渺茫了，不要好高骛远。 再说了，我也没说放弃2进制库的实现，只是暂时不考虑。

无心人

还有就是空间占用 恐怕将来还存在移植问题 10进制移植到64位平台是很困难的 面临改动进制的可能 二进制很可能就改动几个底层汇编就可以了