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倍于被乘数长度的内存，这样在递归调用中不需再次分配。

无心人

你怎么处理负值？