Karatsuba 乘法

Karatsuba 乘法是一种快速的乘法算法,它是由 Anatolii Alexeevitch Karatsuba 在 1960 年发现,并且在 1962 年公开发表的算法

传统的高精度乘法复杂度会达到 n^2,而 Karatsuba 乘法则是基于分治策略,复杂度是 3n^{\log_23},近似值大约为 3n^{1.585}

首先,假设在 B 进制下有两个大整数 a, b,现在我们要计算 a\cdot b

我们可以将其写成


a=a_0\cdot B^m + a_1 \\
b=b_0\cdot B^m + b_1

其中 m 是最小的正整数使得 a_0, a_1, b_0, b_1 < B^m,也就是把 a, b 切成了均匀两半,之后


\begin{eqnarray*}
&&a\cdot b\\
&=&(a_0B^m + a_1)(b_0B^m + b_1)\\
&=&a_0b_0B^{2m}+(a_0b_1+b_0a_1)B^m+a_1b_1\\
&=&a_0b_0B^{2m}+(a_0+a_1)(b_0+b_1)B^m-(a_0b_0+a_1b_1)B^m+a_1b_1
\end{eqnarray*}

到了最后一步,我们发现只需要计算三次乘法 a_0b_0, a_1b_1, (a_0+a_1)(b_0+b_1) 以及六次加法

因此这样复杂度就变为


T(n) = 3T(\frac{n}{2}) + 6n = O(n^{\log_23})

当然这个方法也可以用来计算多项式乘法,你只要认为 B 是多项式的形式变量就好了(而且还不用像高精度那样写个加减进位退位似乎更好写嗯!)

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/10/karatsuba-multiplication

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

2 thoughts on “Karatsuba 乘法

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.