如何解释这个算法计算一个数字的幂？

Question

我目前正在阅读Skiena的“算法设计手册”。

他描述了一种计算数字幂的算法，即计算a^n。

他首先说，最简单的算法就是a*a*a ... *a，所以我们一共进行了n-1计算。

他接着说，这是一种优化，并要求我们认识到：

n = n/2 + n/2

我们也可以说

a^n = ((a^n/2)^2)  (a to the n equals a to the n over 2, squared)

据我所知。从这些方程中，他推导出一种只执行O(lg n)乘法的算法。

function power(a, n)
  if (n = 0) 
    return(1)

  x = power(a,n/2)

  if (n is even)       
    return(x^2)
  else             
    return(a*x^2)

看来x必须是迄今为止计算出来的当前值。但是在读了几遍之后，我还是不明白他是如何从这些方程中设计出这个算法的，甚至也不明白它是如何工作的。有人能解释吗？

Answer 1

首先，让我们修复您的算法：

function power( a, n )
    if (n = 0) 
        return(1)

    x = power(a,n/2)

    if (n is even) 
        return(x*x)
    else 
        return(a*x*x)

假设您想计算power(2,8)，也就是说，2^8 (当然，^不是XOR )。

• ( 1) (a=2，n=8)。2^8 = (2^4)^2，所以我们必须计算x=2^4，然后x*x才能得到最终的结果。我们必须再打电话给power()，才能得到x。power(2,4)。
• 2) (a=2，n=4)。2^4 = (2^2)^2，所以我们必须计算x=2^2，然后x*x才能得到最终的结果。我们必须再打电话给power()，才能得到x。power(2,2)。
• 3) (a=2，n=2)。2^2 = (2^1)^2，所以我们必须计算x=2^1，然后x*x才能得到最终的结果。我们必须再打电话给power()，才能得到x。power(2,1)。
• 4) (a=2，n=1)。2^1 = (2^0)^2，所以我们必须计算x=2^0，然后a*x*x才能得到最终的结果。我们必须再打电话给power()，才能得到x。power(2,0)。
• 5) (a=2，n=0)。2^0 = 1，因为n是0，所以我们有返回到第4步的x值。
• 4) (a=2，n=1，x=1)。这个步骤的最终结果是a*x*x = 2*1*1=2，这是步骤3中要分配给x的值。
• 3) (a=2，n=2，x=2)。这个步骤的最终结果是x*x = 2*2 = 4。这是在步骤2中分配给x的结果。
• 2) (a=2，n=4，x=4)。这个步骤的最终结果是x*x = 4*4 = 16。这是在步骤1中分配给x的结果。
• ( 1) (a=2，n=8，x=16)。这个步骤的最终结果是x*x = 16*16 = 256。这是power(2,8)返回的结果。

Answer 2

x = power(a, n/2)

给出一个^ n/2，如果整条语句被平方，给出( a^n/2 )^2。现在，如果n是奇数，在n/2期间，损失a^1的幂，所以它被乘以a。这是根据给出的方程。

Answer 3

这个函数是递归的，这意味着当被调用时，它会一次又一次地调用自己，直到满足某些最终条件。在本例中，有三个最后的条件将停止函数自身的调用并返回结果。

如果我是你，我会尝试在几个不同的值上手动应用算法，以便理解。