在Python中实现俄罗斯农民乘法的程序
假设给我们四个整数p,q,r和k。我们将使用一种称为俄罗斯农民乘法方法的方法,并确定值(p + q.i)^r = r + s.i。我们必须返回r mod k和s mod k的值。
所以,如果输入如下:p = 3,q = 0,r = 8,k = 10000,则输出将为(6561,0) 3 ^ 8 = 6561,因为q = 0值r mod k = 6561。
为了解决这个问题,我们将按照以下步骤进行:
- 如果r与0相同,则
- 返回1
- 否则,当r等于1时,那么
- 返回一对包含(p mod k,q mod k)的值
- 否则,当r mod 2与0相同时,那么
- 返回solve((p * p-q * q) mod k,2 * p * q mod k,r/2,k)
- 否则,
- 一对(pr,qr) = solve(p,q,r-1,k)
- 返回一个包含((p * pr-q * qr) mod k,(p * qr + q * pr) mod k)的值
示例
让我们看一下以下实现以获得更好的理解——
def solve(p, q, r, k):
if r == 0:
return 1
elif r == 1:
return (p % k, q % k)
elif r % 2 == 0:
return solve((p*p - q*q) % k, 2*p*q % k, r/2, k)
else:
(pr, qr) = solve(p, q, r-1, k)
return ((p * pr - q * qr) % k, (p * qr + q * pr) % k)
print(solve(3, 0, 8, 10000))
输入
3,0,8,10000
输出
(6561,0)