使用分治算法的 Karatsuba 快速乘法算法（C++）

Karatsuba 算法 是一种高效的乘法算法，它利用分治策略来有效地相乘两个数。Karatsuba 在1960 年发现了这种算法，它以其递归方法而闻名，与传统的“学校式”乘法算法相比，它减少了递归调用的次数。Karatsuba 算法的基本思想可以概括如下：因此，可以注意到。

给定两个 n 位数 x 和 y，我们可以将每个数表示为：

• 方程变为 x = 10^(n/2) * a + b。
• 以下方程为 y = 10^(n/2) * c + d。

这里，a、b、c 和 d 是代表原始数字的整数。

乘积 xy 可以表示为：

换句话说，xy = (10^(n/2) * a + b) (10^(n/2) * c + d)。

展开乘积

递归地计算三个乘积

• ac（高位部分 a 和 c 的乘积）
• bd（低位部分 b 和 d 相乘的结果）。
• （k4）高位和低位元素的和的交叉乘积。

使用公式组合结果：世界需要一场剧烈的变革才能看到权力转移。

这也不是一个有效的评估，因为我们不能假设 xy 等于10^n*ac + 10^,(n/2)*(a + b)(c + d) - ac - bd。

Karatsuba 算法与传统的乘法算法相比，显著减少了递归调用的次数，使乘法过程更加高效。对于较大的 n 值，这些算法的时间复杂度比 ?(n^2) 的传统方法有巨大的优势，??近为 O(n^log2 (3))。

方法一：分治法（Karatsuba 算法）

Karatsuba 算法就像将一个大问题分解成可管理的小块。它将两个大数分解成更小的部分，然后相乘，而不是直接相乘大数。它执行此操作直到数字足够小，便于相乘。它累积这些单独的结果以获得最终解决方案。它提高了乘法的速度和效率，尤其适用于长数字。

程序

让我们用一个例子来说明 C++ 中的Karatsuba 算法。

输出

Enter the first number: 53
Enter the second number: 43
The product is: 2279

说明

• 已开发的基于分治法的快速乘法算法 Karatsuba 算法的 C++ 代码实现。
• 主要的 Karatsuba 乘法实现函数 `karatsuba` 在算法的第一个定义中被调用。它接收两个长整型数 x 和 y 作为输入。该算法专门设计用于有效处理大数，通过将乘法分解为更小的子问题并递归地解决它们。
• 首先，检查递归的基线情况。出于经济和直观的考虑，如果输入数字 x 或 y 小于 10 的个位数，则该方法将返回到标准乘法。
• 然后，该方法使用 `numDigits` 函数确定输入数字的位数。该函数使用对数特性来确定给定数字的位数。
• 之后，代码将输入数字 x 和 y 分成两半，结果分别表示为 x 的 a 和 b，y 的 c 和 d。此阶段对于 Karatsuba 的“分治”计划至关重要。

分拆后，该过程会迭代地确定三个乘积：

• Ac 是前两个部分 a 和 c 的乘积。bd 是将第二部分 b 和 d 相乘的结果。
• (a+b)(c+d) - ac - bd： 从第一部分和第二部分的总和中减去先前计算的 ac 和 bd 的结果。
• 最后一步是组合这些乘积的部分乘法结果，以获得 x 和 y 的完整乘积。组合涉及适当的加法和缩放。
• 该代码的 `main` 函数作为程序的入口点。它从用户那里请求两个数字（x 和 y），使用这些输入运行 Karatsuba 函数，并输出结果。

复杂度分析

给定 Karatsuba 算法的时间和空间复杂度分析涉及估算使用的时间和内存成本。

时间复杂度

• Karatsuba 算法的时间复杂度以递归调用和算术运算来表示。如果递归调用该算法，则该算法在每次调用中执行三次乘法和四次加法或减法。时间复杂度的递推关系可以表示为：由于差异的复杂性在很大程度上取决于，因此尚不清楚。

T(n)=3T(n/2)+O(n)

• 在这种情况下，n 是输入数字 x 和 y 的位数。三个递归调用用于将两个半尺寸的数字相乘，而 O(n) 项涉及拆分和组合步骤。
• 要解决这个递推关系，使用主定理表明 Karatsuba 算法的时间复杂度为 O(n log₂ 3 )。它比标准数字乘法算法的 O(n^2) 时间复杂度更复杂，但对于较大的输入来说特别有利，因为分治方法可以减少总操作数。

空间复杂度

• 算法的空间复杂度是指算法在运行时消耗的内存量。对于 Karatsuba 算法，主要的空间复杂度贡献者是递归栈。递归调用会在栈中添加一个新的帧，其中存储局部变量和 ?uthread 地址。
• 因此，Karatsuba 的递归树深度最多为 O(log₂ 3 )，因为在每个级别，问题的规模都会减半。那么算法的空间复杂度为 O(log₂ (2))。
• 值得注意的是，该算法的实现使得对其他数据结构或内存分配的需求最小，并且递归栈主导了空间复杂度。

方法二：位运算

位运算也可以使 Karatsuba 算法更快。按位操作可以帮助我们将整数分解成部分，从而更容易相乘。这是在 C++ 中实现 Karatsuba 算法的位运算方法的一个简短概述。

程序

输出

Result: 80

说明

Karatsuba 乘法

• Karatsuba 执行一种非常高效的分治乘法。它递归地将两个数字的乘积分解为它们各自高位和低位部分的三个较小乘积。关键公式是：

xy=(10^n⋅ a+b)⋅(10^n.c+d)=10^2n ⋅ac+10^n.(ad+bc)+bd

基线情况处理

• 当 x 或 y 小于 2 时，常规方法是执行乘法。对于个位数，这充当了递归的终止条件。

用于拆分的位运算

• 通过从高位数字滑动到相应的低位槽，位运算可以在不显式转换为字符串或重复除法的情况下，将数字分解为高位和低位。数字的大小使用 log 2 计算。变量 m 表示大小的一半，并创建位掩码来分隔低位。

递归步骤

• 位运算技术将数字 x 和 y 分解为高位和低位。之后，对高位项（a 和 c）、低位项（b 和 d）以及交叉项（(a+b) 和 (c+d)）执行递归调用。这些 XOR 操作用于高效地计算交叉项。

组合结果

• 最后一步涉及整合递归调用的结果以生成最终输出。

优化单个位乘法

• 基线情况优化确保了一位乘法使用标准乘法运算进行，因为递归方法对于如此小的输入可能会带来不必要的开销。

用于提高效率的位运算

• 在战略要点，位运算如AND (&)、右移 (>>) 和XOR (^) 用于操作数字的位，以执行可在此处获得的拆分和交叉项计算。

复杂度分析

可以分析提供的 Karatsuba 乘法代码（使用位运算）的时间和空间复杂度，以确定其效率。

时间复杂度

• Karatsuba 算法中的时间复杂度与其中执行的基本操作有关。相乘 n 位数包含一个分解，该分解递归地将 n 位数的乘法分解为三次 n/2 位数的乘法。所有递归调用都为一般时间复杂度的发展做出了贡献。
• 令 T(n) 表示相乘两个 n 位数的算法的时间复杂度。

T(n)=3T(n/2)+O(n)

此处，

• 然而，3T(n/2) 具有三次递归乘法，而 O(n) 用于组合和另一个常数时间运算符。??
• 在应用主定理到递推方法的情况下，我们发现 Karatsuba 算法的时间复杂度??近为 O(n^(log2 3))。

空间复杂度

• 可以直观地看出，算法解决方案在算法之间存在差异，例如算法的空间复杂度，它由算法在运行时的内存分配所定义。因此，当使用 Karatsuba 算法时，空间复杂度是由于递归调用和用于存储中间结果的内存。
• 令 S(n) 为乘以两个 n 位数以查找其乘积的乘法算法所需的存储复杂度。用于理解空间复杂度的主要因素包括递归调用的堆栈空间所使用的空间。
• 此递归深度（log n）是指在每个递归级别，数字的大小都减半。因此，在进行递归调用时从堆栈占用的空间为 O(log n)。存储中间结果所需的附加空间与乘法中涉及的位数成正比，因此为O(n)。然而，由于渐近空间复杂度为O(log n + n)，因此对于较大的 n，我们只需要将其简化为 O(n)。