C++ 俄罗斯农民乘法算法

引言

俄罗斯农夫乘法算法，也称为埃及乘法算法，是一种古老的乘法方法，它依赖于减半和加倍，使其适用于手工计算。它通过重复减半一个数字，并根据特定条件累加结果，将乘法问题分解为一系列更简单的步骤。

它是如何工作的？

俄罗斯农夫乘法算法的核心思想是迭代地将一个数字减半（除以 2），并将另一个数字加倍（乘以 2）。如果减半后的数字是奇数，则将加倍的数字加到结果中。如果减半后的数字是偶数，则丢弃加倍的数字。这个过程一直持续到第一个数字减到 1。

方法 1：简单方法

实施

输出

 
The product of 18 and 25 is: 450   

说明

1. 初始化
   算法开始时，提供两个数字进行乘法。一个数字（a）将进行减半过程，而另一个数字（b）将反复加倍。第三个变量，即结果，初始化为零，它将存储算法进行过程中的累加总和。
2. 主循环执行
   乘法过程围绕一个循环进行，该循环只要 a 大于零就一直继续。循环的每次迭代执行以下任务：
   
   1. a 的奇数检查
      在每次循环迭代开始时，算法会检查 a 是否是奇数。这一点很重要，因为如果 a 是奇数，则需要将 b 的当前值加到累加总和（结果）中。此步骤考虑了当 a 为奇数时，乘法无法整除且没有余数的事实。因此，b 的加倍值代表需要累加的剩余部分。
   2. 减半 a
      接下来，a 被减半，这意味着将其除以 2。在二进制系统中，减半 a 可以看作是通过移除一个精确位数来减小问题。由于乘法可以表示为二进制中的位移，因此减半会逐步减小乘法问题的大小。如果数字是奇数，则舍弃小数部分（因为我们只关心整数）。
   3. 加倍 b
      同时，b 在每次迭代中都会加倍。这个加倍过程补偿了减半 a，因为在 a 减小的同时，b 在增加，以确保两个数字的乘积保持一致。在每次迭代中，将 b 加倍可以视为乘以 2。
3. 累加总和（结果）
   如前所述，如果在任何迭代中 a 为奇数，则将 b 的当前值加到结果中。这种累加对于确保最终答案包括所有不能仅通过减半过程处理的乘法部分（即当 a 为奇数时）至关重要。如果 a 为偶数，则不进行加法，循环将移至下一次迭代。
4. 循环继续
   循环重复这些步骤——减半 a、加倍 b、检查 a 是否为奇数以及更新结果——直到 a 减到零或一。如果 a 在最后一步为一，则将 b 的值加到结果中，因为乘法现已简化为最终形式。
5. 最终输出
   循环完成后，result 变量将保存 a 和 b 原始值的乘积。之所以有效，是因为该过程通过减半和加倍有效地将乘法分解为易于管理的块，并且它确保任何剩余部分（来自 a 的奇数值）都可以通过添加相应的 b 值来处理。

复杂度分析

时间复杂度

减半和加倍

• 在每次迭代中，算法将 a 减半并将 b 加倍。减半 a 会显著减小问题规模，因为每次除以 2 都会将 a 减小 2 的倍数。
• 在 a 变为零之前，可以减半 a 的次数与 log a 成正比，具体为 O(log a)。

奇数检查和加法

• 检查 a 是否为奇数是一次恒定时间操作，O(1)。
• 将 b 添加到结果中也是恒定时间，O(1)。

因此，算法在每次迭代中执行恒定的工作量，并且迭代次数与 log a 成正比。因此，总时间复杂度为 O(log a)。

空间复杂度

俄罗斯农夫乘法算法只使用少数几个额外的变量，例如 result 和 a、b 的临时副本。这些变量占用恒定的空间。

• 没有使用额外的数组或动态数据结构。
• 所需的内存量不会随着输入数字的大小而增长。

因此，无论输入数字的大小如何，空间复杂度均为 O(1)（常数空间）。

方法 2：使用 Karatsuba 算法

Karatsuba 算法通过将较大的数字分解成更小的部分，使用更少的乘法来降低乘法的时间复杂度。它利用了这样一个观点：两个数字的乘积可以通过将数字分解成更小的部分，将这些部分相乘，然后合并结果来计算。该算法实现了比标准乘法更好的时间复杂度，即两个 n 位数字的乘法为 O(n²)。

实施

输出

 
Product of 1234 and 5678 is: 7006652   

说明

1. 理解问题
   我们试图将两个大数字相乘。Karatsuba 算法不是使用传统的长乘法（其时间与数字位数平方成正比），而是将问题分解成更小的部分，并使用分治法更有效地解决它。
2. 分解数字
   该算法通过将两个数字分成两部分来工作。如果数字很大（假设都是四位数），则将它们分成高位和低位两部分。
   例如
   
   • 对于 x = 1234，将其分解为 x1 = 12（高位部分）和 x0 = 34（低位部分）。
   • 对于 y = 5678，将其分解为 y1 = 56（高位部分）和 y0 = 78（低位部分）。

通过分割数字，我们可以将乘法问题表示为

其中 m 是低位部分的位数（例如，在此例中 m = 2）。

3. 三次主要乘法

要使用此公式计算两个数字的乘积，我们需要三次乘法：

• z2：这是高位部分 (x1 * y1) 的乘积。
• z0：这是低位部分 (x0 * y0) 的乘积。
• z1：这是部分和的乘积
• 首先，计算 (x1 + x0) 和 (y1 + y0)。
• 然后将这些和相乘。
• 从该结果中减去先前计算的 z2 和 z0。

这给出了中间项，这对于有效合并三个结果至关重要。

4. 递归调用

这三次乘法（z2、z0 和 z1）中的每一次都涉及比原始问题更小的数字。如果这些数字仍然很大，算法将递归地调用自身，进一步分割数字，直到它们足够小可以进行直接乘法。

这种递归是算法效率的来源——通过将大乘法分解为小乘法，整体时间复杂度得以降低。

5. 合并结果

一旦计算出三个部分（z2、z0 和 z1），算法就会将它们合并以获得最终乘积。合并方式如下：

• z2 乘以 10^(2*m)（左移 2*m 位）。
• z1 乘以 10^m（左移 m 位）。
• 最后，将所有三个项（z2、z1 和 z0）相加，形成最终乘积。

6. 辅助函数

由于数字以字符串形式处理（以管理大值），因此算法包含以下辅助函数：

• 填充零：这确保在执行运算时两个数字具有相同的位数。
• 字符串加法：将两个存储为字符串的大数字相加。
• 字符串减法：将一个大字符串数字从另一个字符串数字中减去。

这些辅助函数对于在不溢出数据类型限制的情况下处理大数字至关重要。

7. 基本情况

递归停止在数字足够小以进行直接乘法时（即，个位数）。当这种情况发生时，算法执行基本乘法并返回结果。

8. 最后一步

在递归调用和三次乘法（z2、z1 和 z0）之后，将结果合并以得出最终答案。这种分割、递归乘法和合并的过程一直持续到所有递归调用都得到解决。

复杂度分析

时间复杂度

递归：Karatsuba 算法递归地将数字分成两半，直到它们足够小可以进行直接乘法。

• 对于每次递归调用，输入大小都会减半。
• 它在每次递归步骤中执行三次乘法，而不是传统的四次。

对数深度：如果输入数字有 n 位，则递归深度为 log₂(n)，因为每次输入大小都会减半。

乘法成本：在每个递归级别，都会对大小减半的数字执行三次乘法，并且这种过程会沿着递归树一直向下进行。合并结果（通过加法和减法）的成本在每个级别都是线性的。

总时间复杂度：总时间复杂度由 O(n^log₂3) 给出，简化为大约 O(n^1.585)。这比传统乘法处理大数字时的 O(n²) 复杂度要好得多。

空间复杂度

递归堆栈：由于该算法使用递归，因此递归堆栈所需的空间取决于递归的深度。

• 由于每次递归步骤都会将输入大小减半，因此递归深度为 log₂(n)。

临时存储：在每次递归调用中，都需要空间来存储中间结果（例如 z2、z1 和 z0），以及加法和减法运算的结果。

总空间复杂度：由于递归函数调用的内存需求以及加法和减法运算期间的中间结果存储，空间复杂度为 O(n)。