Java实现Karatsuba乘法：两位数计算正常、多位数结果错误求助

你代码在算出78 * 34 = 2652这个正确结果后开始出现整体偏差，本质是对Karatsuba乘法的拆分规则、幂次计算逻辑的理解存在偏差，具体问题出在三处：

• 拆分逻辑错位
  Karatsuba乘法要求先统一两个数的拆分基准：取两个数的最大位数，向上凑成偶数长度，用同一个半长值把两个数拆成高位、低位两部分。你的代码是分别拿每个数自己的长度除以2算拆分位置，完全没有统一基准。
  举个你实际触发bug的场景：递归算到134 * 46这步时，两个数的长度分别是3、2，按照规则应该凑成4位总长度，取半长2，把两个数都补成4位再拆分。但你的代码是给长度3的134按自身长度算半长1，拆成高位1、低位34；给长度2的46按自身长度算半长1，拆成高位4、低位6，拆分出来的高位、低位边界完全错位，后面的递归计算从根上就不对。
• 幂次乘算参数错配
  Karatsuba的最终计算规则是：

  总乘积 = 高位相乘的结果 * 10^(2m) + 中间差值的结果 * 10^m + 低位相乘的结果
  这里的m是刚才统一拆分用的半长。你的代码是拿两个数的最大总长度n，用10^{n乘高位乘积，用10}(n/2)乘中间差值。之前算两位数的时候n=2，2m=2，结果刚好能对上，一旦遇到总长度是奇数、拆分半长和总长度不匹配的场景，乘的幂次就完全错了。比如总长度是3的时候，整数除法算n/2=1，你实际乘的是10^{1，根本不是公式要求的对应半长的10}m。

• 浮点数算幂次的精度隐患
  你用返回double类型的Math.pow计算10的幂次，当处理的数字位数比较多时，double的有限精度会导致数值偏差，转成BigInteger之后的结果不准，位数越高偏差越大。

• 先取两个数的字符串长度，算最大值，向上凑成偶数长度（比如长度为3就补到4），统一计算拆分用的半长m = 凑完的偶数长度 / 2
• 把两个数的字符串前面补0，凑到统一的偶数长度，再按照同一个m值拆分出高位a、低位b，高位c、低位d
• 计算10的幂次时直接用BigInteger.TEN.pow(幂次值)，不要用double类型的数学方法计算幂次
• 删掉之前按单个字符串长度分别计算拆分位置的逻辑，所有拆分步骤使用统一的m值

内容的提问来源于stack exchange，提问作者Haritha