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

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

这个概念很简单.例如,计算3 ⁸的值

您可以使用明显的方法,即3 ⁸ = 3 x 3 x 3 x 3 x 3 x 3 x 3 x 3,这需要7次乘法运算.或者有更好的方法.

我们这样说吧

• 如果我们知道值3 ⁴,我们只能在一次乘法运算中计算3 ⁸,但我们不知道3 ⁴的值
• 如果我们知道3 ²的值,我们可以在一次乘法运算中计算3 ⁴.
• 最后,我们知道3 ²可以轻松计算3 x 3.

向后看,只需要3次乘法来计算3 ⁸而不是7

以下是该过程的清晰视图:

   32 = 3 x 3 = 9
   34 = 32 x 32 = 9 x 9 = 81
   38 = 34 x 34 = 81 x 81 = 6,561

然后,还有另一个问题,如果功率是奇数,该怎么办？例如:3 ⁹,如何处理它？你可以这样做

   39 = 3 x 38   or
   39 = 3 x 34 x 34

让我们称之为连续多为数字算法方法A算法,并连续由两个作为划分功率方法B.方法A与方法B相比有多好？对于少数如3 ⁸,没有太大的改进,即使是那些,我们最小化乘法的数量,但我们也略微增加除法运算的数量.

所以3 ⁸

               Multiplication   Division
   Method A:        7              0
   Method B:        3              3

但是,对于较大的功率,例如:3 ^{4,294,967,296}

               Multiplication   Division
   Method A:   4,294,967,295       0
   Method B:       32              32

差异很大.

Answer 2

首先,让我们修复你的算法:

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,所以我们将其值x返回到第4步.

• 4)( , a=2,).n=1 x=1此步骤的最终结果是a*x*x = 2*1*1=2,x在步骤#3中分配的值.

• 3)( , a=2,).n=2 x=2这一步的最终结果是x*x = 2*2 = 4.这是x在步骤#2中分配的结果.

• 2)( , a=2,).n=4 x=4这一步的最终结果是x*x = 4*4 = 16.这是x在步骤#1中分配的结果.

• 1)( , a=2,).n=8 x=16这一步的最终结果是x*x = 16*16 = 256.这是返回的结果power(2,8).