karatsuba乘法两种算法比较测试

无心人

对于乘法的karatsuba乘法目前有两种表示方法

设$A = a_1 * 2^k + a_0, B = b_1 * 2^k + b_0, C = A * B = c_2 * 2^{2k} + c_1 * 2^k + c_0$

其中$c_2 = a_1 * b_1, c_0 = a_0 * b_0$

但是$c_1$有两种表示

1、$c_1 = (a_1 + a_0) * (b_1 + b_0) - (c_2 + c_0)$
2、$c_1 = (a_1 - a_0) * (b_0 - b_1) + (c_2 + c_0)$

目前的问题是，两种表示方式在实际的程序设计和最后使用上是否存在差异，选择哪个合适呢？

gxqcn

应该说两个都可，都有各自优缺点。

用第2种形式缺点是需要进行有符号运算，优点是中间临时变量需要的空间小于前者。

HugeCalc 当前内部用的是第2种形式，但我现在更倾向于用第1种形式，
因为实际上，两数之差可以缩减数字有效长度的概率很低，用第1种形式可以简化算法设计。

无心人

第2种形式的符号变换很简单的
存在很快的汇编代码做这个
比减法快很多很多的

我也实现的是2

gxqcn

我估计你说的“汇编代码”是指：

1、从低位向高位两数直接相减；
2、如果最后的需要借位，但被减数已无位可借时，
　2.1、设某个标记，为负；
　2.2、将当前结果的每个数用 neg 指令；
　否则，直接转入后续步骤；
3、。。。

上述算法可以避免先比较大小再相减，
但在结果为负时仍需修正，且仅适合内部进制bit数正好为系统字长的情况。

不知我猜的可对？

无心人

对

不过你说的做法不对

是先对数字串每个都求反，这个可并行操作，一次求4个128位的
然后执行加1操作

gxqcn

如此看来，第2种形式不如第1种形式简洁高效。

无心人

是否存在比较的必要？

考虑工作量
1、前加法2k 乘法(k+1)^2 后加法2k 总减法 2k+1
2、前减法2k 纠正2k+2 乘法k^2 后加法2k 总加法 2k+1
差异在
1、乘法(k+1)^2
2、纠正2k+2 乘法k^2

(k+1)^2 - k^2 - (2k+2) = -1
所以2的理论工作量大于1

无心人

但考虑概率因素
即纠正不是总是发生

则2的纠正假设概率是1/2

则实际的纠正工作量是k+1

则此时2小于1

=================
考虑实际情况，此时的k总是大于1的

liangbch

我用的是第二个格式，很多程序也用的是第二种格式，我想第二种形式应该更好吧。
  第二种形式 在确定临时内存空间的大小时很简单，可以预先一次分配所需的内存。我的做法是一次分配4倍于被乘数长度的内存，这样在递归调用中不需再次分配。

无心人

你怎么处理负值？