算法之两个大正整数相乘Karatsuba算法

[front-thinking]

算法之两个大正整数相乘Karatsuba算法

经常做算法题的朋友都知道，几乎所有的互联网公司面试笔试都会遇到一类题目或者题目的变种叫做大正整数相乘。题目看似非常简单，就是给你两个大的正整数，让你设计算法计算出来他的结果。我们从小大概三年级就学习了乘法，依次用乘数去成被乘数，最后相加得结果。但是，作为一名立志写出更牛逼的代码的码农，还是要在做完的时候经常问自己是否能做的更好。今天我们就讲解一下大正整数相乘的Karatsuba算法。

引导

老习惯，照例我们先列出题目来：

输入： 两个大正整数x和y
输出： x和y的结果

解决思路一

我们看看，我们从小就学习到的乘法是如何解决的，例如5678*1234：

            5678
           *1234
        -----------
           22712
         17034
        11356
        5678
---------------
       7006652

这就是我们小时候学习的解决方法，很简单，也不复杂。这里需要考虑的问题就是n位乘以n位的了，并且需要处理好其中的进位就好。
但是，凡是都有个但是。但是这里，我们能不能做的更好一些。仔细看这里就很容易知道，这里的算法复杂度至少是O（n的平方）。我们能不能有更好的解决方法呢？

解决思路二

答案是肯定有，否则今天就不用继续写下去了。这就是我们今天要介绍的Karatsuba算法，Karatsuba是Anatoly Karatsuba这个小伙子在1960年大概是他23岁的样子的时候提出来的算法，因此命名为Karatsuba算法。这里，跟我们之前介绍归并排序算法的时候一样，用的是分治策略。简单的讲，就是把两个大数各个都分解为两个部分，来优化乘法。好了，不废话了，开始讲Karatsuba的算法。

Karatsuba算法

假设两个大整数x和y，分别都是n位长度。假设x分为两个部门，高阶部分为a，低阶部分为b，y也一样高阶为c，低阶为d。比方说我们刚才提到的5678和1234，那么a就是56，b是78，c是12，d是34。那么xy=(10的n/2次方 * a + b) * (10的n/2次方 * c + d) = 10的n次方 * （a * c） + 10的n/2次方 * （a * d + bc） + bd，这里由于（a + b）(c + d) - a * c - bd =ac + ad + bc + bd - ac - bd = ad + bc ,所以ad + bc可以通过计算（a + b）(c + d) - a * c - bd来获取。那么原来需要nn位的减少为只需要减少为计算ac、bd和（a+b）(c +d)了，这三个计算继续递归调用自身做计算即可。

伪代码

// 输入：n位长度的正整数x和y
// 输出：x*y的结果
函数 karatsuba (x, y) {
     a和b为x的前半部分和后半部分；
     c和d是y的前半部分和后半部分；
    递归调用函数karatsuba解决q=a*c， 递归karatsuba解决p=b*d，递归karatsuba解决k=(a+b)(c+d)
    返回10的n次方*q + 10的n/2次方 * (k - q - p) + p

}

karatsuba算法之JavaScript实现

function karatsuba (x, y) {
  var x = x + '', y = y + '';
  var n = x.length, a, b, c, d, p, q, i = Math.pow(10, n/2), a1, b1, c1;
  if (n === 1) {
    return +x * +y;
  } else {
    a = Math.floor(+x/i), b = +x%i, c = Math.floor(+y/i), d = +y%i, p = a + b, q = c + d;
    a1 = karatsuba(a, c), b1 = karatsuba(b,d), c1 = karatsuba(p,q);
    return Math.pow(10, n)*a1 + i * (c1 - a1 -b1) + b1;
  }
}

结束语

期初听起来超费劲的karatsuba算法其实并没有传起来那么复杂，根本的优化在于利用数学中的结合律等来优化了代码部分。沉下心来，其实很多复杂的算法问题，最终都是使用比较简单的解决思路。