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

Introduction to Karatsuba Algorithm

The Karatsuba algorithm, a foundational method for performing efficient multiplication of large numbers in computer science¹. 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.

Karatsuba算法是计算机科学中用于进行大数乘法的基础高效方法¹。在科罗拉多大学波尔德分校的动态规划和贪心算法课程的第一周里教授了这个算法。这个算法证明了分治策略的威力。

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.

在以下部分，我们将深入研究Karatsuba算法的机制，讨论其复杂性，并检查这个算法真正发光的应用。

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。

Input:

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

Output:

The product of 1234 and 5678 is 7006652.

Code Resources

• https://github.com/MisakaBit/CUBoulder-MSCS/blob/main/Karatsuba%20Multiplication%20Algorithm.ipynb

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.

除了传统的乘法算法外，我们还介绍了Karatsuba算法的思想。Karatsuba算法利用分治的思想，将大数的乘法问题分解为更小的子问题，并通过递归求解这些子问题来获得最终结果。这种算法在某些情况下可以显著减少乘法的运算次数，从而提高算法的效率。

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.

这些算法不仅可以有效地处理大数运算，而且在密码学等领域中经常需要进行这样的计算。掌握这些算法不仅可以帮助我们更好地理解数字运算的本质，还可以应用于解决实际的工程和科学问题。

Reference

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