在Python中实现俄罗斯农民乘法的程序

在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)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程