俄罗斯农民乘法算法的时间效率

Question

从时间效率的角度来看，Russian peasant multiplication算法是n乘以m还是m乘以n有关系吗？

比如，计算26*47时，时间效率和计算47*26差不多吗？

Answer 1

由于算法运行s floor(log2(k)) 次迭代 k 的乘数（第一个数字），运行时间肯定取决于顺序。如果 n 和 m 位于相同的两个连续的 2 的幂之间，那么它们将需要相同的迭代次数才能完成。否则，始终将较小的数字放在第一位以尽量减少运行时间。

Answer 2

unsigned int russianPeasant(unsigned int a, unsigned int b) { 
    int res = 0;  // initialize result 
    // While second number doesn't become 1 
    while (b > 0) 
    { 
         // If second number becomes odd, add the first number to result 
         if (b & 1) 
             res = res + a; 
         // Double the first number and halve the second number 
         a = a << 1; 
         b = b >> 1; 
     } 
     return res; 
}

算法在b变为0时退出while循环，循环运行次数为[log2(b)] + 1次

并且换档几乎需要常数时间（1 CPU 周期）

用较小的值作为b来调用是有意义的。

奖励：速度比较

我写了上面的代码和运行相同的数字47和26循环了10**8次。

a = 26，b=47，平均耗时 1336852.2 微秒。

a = 47，b=26，平均耗时 1094454.4 微秒。

有趣的旁注：

虽然正如@Dillon Davis 提到的那样，如果他们的日志相同，它应该需要相同的迭代次数，但我发现它仍然需要更少的时间和更少的数字作为 b。

（所有时间以微秒为单位）
a = 46,b = 36 - 1204240.6
a = 36, b = 46 - 1295766.8

a=44，b=36 - 1204266.2
a= 36, b = 44 - 1253821.17.

TLDR: 运行第二个数字较小（while 循环中的那个）

源代码来自：https://www.geeksforgeeks.org/russian-peasant-multiply-two-numbers-using-bitwise-operators/

Answer 3

这取决于您如何实施俄罗斯农民算法。可以是：

a*b 更快
b*a 更快
没有区别

我选择 没有区别，因为实数的数学乘法是可交换的：a*b=b*a 并且因为最终用户在调用您的函数时不喜欢为参数的顺序烦恼

为此，您需要像这样调整代码：

Let the two given numbers be 'a' and 'b'.
1) If 'b' is greater than 'a' - swap 'a' with 'b'
2) Initialize result 'res' as 0.
3) Do following while 'b' is greater than 0
   a) If 'b' is odd, add 'a' to 'res'
   b) Double 'a' and halve 'b'
4) Return 'res'.

这段代码会比较复杂

O(log₂(min(a,b)))

俄罗斯农民乘法算法的时间效率

Time efficiency of the Russian peasant multiplication algorithm

language-agnostic

algorithm