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

Question

从时间效率的角度来看，用Russian peasant multiplication算法将n乘以m或m乘以n是否重要？

例如，当计算26 * 47时，时间效率类似于计算47 * 26？

Answer 1

由于该算法针对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 2（min（a，b）））