Python实现俄罗斯农民乘法

俄罗斯农民乘法又称为双倍增量算法，是一种快速的乘法算法。相较于标准的竖式乘法，其速度更快。下面将介绍如何在Python中实现俄罗斯农民乘法的程序。

算法原理

俄罗斯农民乘法的原理是将两个数递归地不断地取半，一半取整，另一半取余，直到其中的一半为1。最后再将剩余的整数部分都相加即为乘积。例如，将10和7相乘，可以按照如下方式进行：

10和7分别除以2得到5和3，分别写在两列的左边；
5再除以2得到2，余1；3再除以2得到1，余1，这些余数写在两列的右边；
将右边列中的所有数相加，即1+1+3=5；

最终答案即为左边列中的所有整数相加，即5。

代码实现

下面是Python中俄罗斯农民乘法的程序实现：

def russian_peasant_mult(x, y):
    result = 0
    while y > 0:
        if y & 1:
            result += x
        x <<= 1
        y >>= 1
    return result

该程序接受两个参数x和y，代表需要相乘的两个数。使用位运算符来判断y是否为奇数，如果是则将x加到结果result中。然后将x乘以2，将y除以2，直到y为0。

测试样例

下面是几个测试样例：

assert russian_peasant_mult(2, 3) == 6
assert russian_peasant_mult(123456, 789) == 97463504
assert russian_peasant_mult(123456789, 987654321) == 121932631137021789
assert russian_peasant_mult(0, 123) == 0
assert russian_peasant_mult(123, 0) == 0