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)$
目前的问题是，两种表示方式在实际的程序设计和最后使用上是否存在差异，选择哪个合适呢？ 应该说两个都可，都有各自优缺点。
用第2种形式缺点是需要进行有符号运算，优点是中间临时变量需要的空间小于前者。
HugeCalc 当前内部用的是第2种形式，但我现在更倾向于用第1种形式，
因为实际上，两数之差可以缩减数字有效长度的概率很低，用第1种形式可以简化算法设计。 第2种形式的符号变换很简单的
存在很快的汇编代码做这个
比减法快很多很多的
我也实现的是2 我估计你说的“汇编代码”是指：
1、从低位向高位两数直接相减；
2、如果最后的需要借位，但被减数已无位可借时，
2.1、设某个标记，为负；
2.2、将当前结果的每个数用 neg 指令；
否则，直接转入后续步骤；
3、。。。
上述算法可以避免先比较大小再相减，
但在结果为负时仍需修正，且仅适合内部进制bit数正好为系统字长的情况。
不知我猜的可对？ 对
不过你说的做法不对
是先对数字串每个都求反，这个可并行操作，一次求4个128位的
然后执行加1操作 如此看来，第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的 我用的是第二个格式，很多程序也用的是第二种格式，我想第二种形式应该更好吧。
第二种形式 在确定临时内存空间的大小时很简单，可以预先一次分配所需的内存。我的做法是一次分配4倍于被乘数长度的内存，这样在递归调用中不需再次分配。 :)
你怎么处理负值？