C语言实现Comba乘法算法的问题
在大整数乘法的初等算法中，除了基础的笔算乘法算法外，比较优秀的有“Comba算法”。与基础的笔算乘法不同的是，笔算乘法算法是行为单位进行计算，而Comba算法是以列为单位进行计算的，Comba算法本身的原理比较简单，就是通过对乘法竖式中的每列进行累加，不用每计算一次乘积都要更新本位并向高位传递进位，从而可达到加速乘法的目的。我认为Comba算法最吸引人的地方是，它基本上在任何规模下都比基础笔算乘法快，这一点是karatsuba，Toom-Cook，FFT等高级算法不具备的。而且，在karatsuba，Toom-Cook算法中递归到小规模时也要用笔算乘法或Comba算法返回，所以，实现高效的Comba算法对于加速karatsuba，Toom-Cook算法也具有一定的意义。
在我的实现中，大整数以2^32为基，每两个元素之积就已经有64bits，因此要让Comba算法有效，必须实现一个高效的96bits的累加器（或能够高效模拟也行），可C语言本身没有96bits的变量，我采用的方法是用一个unsigned long long型的变量ctotal来保存低64bits，用一个unsigned int型变量carry来保存高32bits，每次将积basetmp加到ctotal上(ctotal+=basetmp)，如果ctotal<basetmp，则说明有进位，将变量carry加1。计算每列的核心代码如下所示：

basetmp=(unsigned long long)pright[rpos]*pleft[lpos]; //pright, pleft为参与乘法运算的大整数
ctotal+=basetmp;
if (ctotal<basetmp) //如果条件满足，说明有溢出，将高32bits加上1
++carry;

上述算法通过VC 2010编译通过，经过测试，这种算法效率比较低，比基础的笔算乘法还要慢50%左右。反复研究后知道，就是因为两个64bits的无符号整数比较大小（语句：if (ctotal<basetmp)）效率低使整个算法慢下来。

因此，特向大家请教如何高效实现Comba算法。

[解决办法]
桑哥好人 桑哥一生平安...