算法 1 ： 乘法算法

Karatsuba Multiplication

karatsuba算法，快速相乘算法。由Anatolii Alexeevitch Karatsuba在1960年提出。[1][2][3]其复杂度为 $ 3n^{\log_{2} 3} $。快于经典乘法。

我们在python的long的乘法中可以见到这个算法：

其基本原理

将位数较大的两个大数x和y分成位数较少的数「一半一半」，将其简化为做3次乘法。


{{- code -}}

  1. A. Karatsuba and Yu. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Proceedings of the USSR Academy of Sciences. 1962, 145: 293–294. ↩︎

  2. A. A. Karatsuba. The Complexity of Computations (PDF). Proceedings of the Steklov Institute of Mathematics. 1995, 211: 169–183. ↩︎

  3. Knuth D.E.（1969）The art of computer programming. v.2. Addison-Wesley Publ.Co., 724 pp. ↩︎