使用递归计算大数的幂

Question

目标是使用递归计算提高到其他大位数的大位数，例如，将 100 位数提高到另一个 100 位数。

我的计划是递归计算 exp/2，其中 exp 是指数，并根据 exp 是偶数还是奇数进行额外计算。

我当前的代码是：

def power(y, x, n):
    #Base Case
    if x == 0:
        return 1

    #If d is even
    if (x%2==0): 
        m = power(y, x//2, n)
        #Print statment only used as check
        print(x, m)
        return m*m

    #If d is odd
    else:
        m = y*power(y, x//2, n)
        #Print statement only used as check
        print(x, m)
        return m*m

我运行遇到的问题是它进行了太多的计算，我正在努力弄清楚如何解决它。例如2^3returns64、2^4returns256、2^5returns1024等等。它计算 m*m 的次数太多了。

注意：这是求解大数取模的一部分。我正在严格测试代码的指数部分。

Answer 1

首先，您的实现有一个奇怪的地方：您使用了一个您从未使用过的参数 n，但只是继续传递并且您从不 modify。

其次，第二次递归调用不正确：

else:
    m = y*power(y, x//2, n)
    #Print statement only used as check
    print(x, m)
    return m*m

如果你算一下，你会发现你 return: (y y^x//2)²=y^2*(x//2+1)（注意 // 而不是 /）这是因此 y 太多了。为了正确执行此操作，您应该将其重写为：

else:
    m = power(y, x//2, n)
    #Print statement only used as check
    print(x, m)
    return y*m*m

（因此从 m 部分中删除 y* 并将其添加到 return 语句中，这样它就不会平方）。

这样做将使您的实现至少在语义上是合理的。但是不会解决performance/memory方面的问题。

你的明确表示你想对结果做 modulo，所以这可能是 Project Euler?

策略是利用 modulo 在乘法下封闭的事实。换句话说，以下成立：

(a b) mod c = ((a mod c) * (b mod c)) mod c

您可以在您的程序中使用它来防止生成 巨大的数字 ，从而处理需要很少计算工作的小数字运行。

另一个优化是您可以在参数中简单地使用正方形。所以更快的实现是这样的：

def power(y, x, n):
    if x == 0: #base case
        return 1
    elif (x%2==0): #x even 
        return power((y*y)%n,x//2,n)%n
    else: #x odd
        return (y*power((y*y)%n,x//2,n))%n

如果我们用这个函数做一个小测试，我们看到两个结果对于小数字是相同的（其中 pow() 可以在合理的 time/memory 中处理）：(12347**2742)%1009 returns 787L和power(12347,2742,1009) 787，所以他们产生的结果是一样的（当然这不是proof），即两者是等价的，只是一个简短的测试，可以过滤掉明显的错误。

Answer 2

根据这个问题的 c 版本，这是我的方法，它适用于正指数和负指数：

def power(a,b):
  """this function will raise a to the power b but recursivelly"""
  #first of all we need to verify the input
  if isinstance(a,(int,float)) and isinstance(b,int):
    if a==0:
      #to gain time
      return 0
    if b==0:
        return 1
    if b >0:
      if (b%2==0): 
      #this will reduce time by 2 when number are even and it just calculate the power of one part and then multiply 
        if b==2:
          return a*a
        else:
          return power(power(a,b/2),2)
      else:
      #the main case when the number is odd
        return a * power(a, b- 1)
    elif not b >0:
      #this is for negatives exposents
      return 1./float(power(a,-b))
  else:
    raise TypeError('Argument must be interfer or float')

使用递归计算大数的幂

Using recursion to calculate powers of large digit numbers

python

recursion

exponent