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位平台是很困难的
面临改动进制的可能
二进制很可能就改动几个底层汇编就可以了