Karatsuba Algorithm(卡拉丘巴乘法算法)

Introduction to Karatsuba Algorithm

The Karatsuba algorithm, a foundational method for performing efficient multiplication of large numbers in computer science1. Taught in Week 1 of the Dynamic Programming and Greedy Algorithms course at CU Boulder, the algorithm stands as a testament to the power of a divide-and-conquer strategy.


The Karatsuba algorithm, named after Anatolii Alexeevitch Karatsuba, strategically breaks down the task of multiplying two n-digit numbers into simpler subtasks, avoiding the traditional computational complexity of multiplication. This approach illustrates the multiplicative properties of numbers and the time-saving potentials of recursion and divide-and-conquer techniques in algorithm development.

Karatsuba算法是以Anatolii Alexeevitch Karatsuba命名的,该算法巧妙地将两个n位数的乘法任务分解为更简单的子任务,从而避免了乘法的传统计算复杂性。这种方法说明了数字的乘法性质,以及在算法开发中递归和分治技术的节省时间的潜力。

In the following sections, we will delve into the mechanics of the Karatsuba algorithm, discuss its complexity, and examine applications where this algorithm truly shines.


The Mechanics of Karatsuba Algorithm

The Karatsuba algorithm commences multiplication by splitting both numbers into two halves. The upper half (most significant digits) is labeled as ‘a’ and ‘c’, and the lower half (least significant digits) is correspondingly ‘b’ and ‘d’. The algorithm breaks the traditional multiplication into three main multiplications, namely, ac, bd, and (a+b)(c+d). Calculation of (a+b)(c+d) results in obtaining the sum of ac, bd, and a pair of cross products (ad+bc). To receive the final result, ac is shifted left by m digits (where m is the number of digits in smaller half), and bd stays unaltered. This makes the algorithm faster than classical multiplication for sufficiently large numbers.

Karatsuba算法首先通过将两个数字分为两半来开始乘法运算。上半部分(最显著的数字)被标记为’a’和’c’,下半部分(最不显著的数字)相应地被标记为’b’和’d’。该算法将传统的乘法运算分解为三个主要的乘法运算,即ac, bd, 和(a+b)(c+d)。计算(a+b)(c+d)的结果是获得ac, bd, 和一对交叉乘积(ad+bc)的和。为了得到最终的结果,ac被向左移m位(其中m是较小的一半中的数字的位数),而bd保持不变。这使得对于足够大的数字,该算法比传统的乘法运算快。

Karatsuba Multiplication Example

Here is an example that demonstrates how to use Karatsuba’s algorithm to calculate the multiplication of larger numbers. Let’s take the example of multiplying two 4-digit numbers: let’s say we want to calculate 1234 * 5678.

这是一个示例,演示了如何使用Karatsuba算法来计算较大数字的乘法。我们以两个4位数相乘为例:假设我们要计算 1234 * 5678。


Let’s consider two numbers:

  • a = 1234
  • b = 5678

Step 1: Splitting the Numbers

  1. Split each number into two halves:
    • a = 12, 34
    • b = 56, 78

Step 2: Calculate Three Products

  1. Calculate ac: 12 * 56 = 672
  2. Calculate bd: 34 * 78 = 2652
  3. Calculate (a+b)(c+d): (12+34)(56+78) = 46 * 134 = 6164

Step 3: Calculate Cross Products (交叉乘积)

  1. Subtract ac and bd from (a+b)(c+d):
    • 6164 - 672 = 5492
    • 5492 - 2652 = 2840

Step 4: Combine Results

  1. Shift ac left by the number of digits in smaller half:
    • Shift 672 left by 2 digits: 67200
  2. Add the results:
    • ac * 10^4 + (ad+bc) * 10^2 + bd = 67200 + 2840 * 100 + 2652 = 7006652


The product of 1234 and 5678 is 7006652.

Code Resources

Wrapping Up the Discussion

In this course, we delved into the operations of addition and multiplication for large numbers. Large numbers refer to numbers longer than the computer’s word length, and they find wide applications in various real-world scenarios, particularly in fields like cryptography.


  • Addition Algorithm

    • The addition algorithm involves adding digits starting from the least significant bit and considering carryovers. If there’s a carryover, it gets added to the next digit’s calculation. Eventually, we obtain the sum of two large numbers.


  • Multiplication Algorithm

    • For multiplication, we employ a method known as “vertical multiplication.” Each digit of one large number is multiplied with every digit of the other, and the results are added up. Carryovers are handled similarly to addition. Ultimately, we arrive at the product of two large numbers.
  • 乘法算法使用了一种称为“竖式乘法”的方法来进行乘法运算。我们将一个大数的每一位与另一个大数的每一位相乘,并将结果相加。如果有进位,则将进位加到下一位的运算中。最终,我们得到的结果就是两个大数的乘积。
  • Karatsuba Algorithm
    • In addition to the traditional multiplication algorithm, we also introduced the Karatsuba algorithm. The Karatsuba algorithm utilizes the divide-and-conquer approach, breaking down the multiplication problem of large numbers into smaller subproblems. By recursively solving these subproblems, the final result is obtained. This algorithm can significantly reduce the number of multiplication operations in certain cases, thus enhancing efficiency.


These algorithms not only effectively handle operations with large numbers but are also frequently required in fields like cryptography. Mastering these algorithms not only deepens our understanding of numerical operations but also allows us to apply this knowledge to solve practical engineering and scientific problems.



1 Karatsuba, Anatolii Alexeevitch. “The Complexity of Multiplication in Generic Algebras.” Proceedings of Steklov Institute of Mathematics 211 (1995): 169-183.