如何解释这种计算数字幂的算法？ [英] How to explain this algorithm for calculating the power of a number?

问题描述

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

I am currently reading Skiena's "The Algorithm Design Manual".

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

He describes an algorithm for calculating the power of a number i.e. calculate a^n.

他首先说，最简单的算法就是 a * a * a ... * a ，因此我们总共有 n-1 个计算。

He begins by saying that the simplest algorithm is simply a*a*a ... *a, so we have a total of n-1 calculations.

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

He then goes on to say that there is an optimisation for that, and asks us to recognise that:

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）乘法的算法。

Which I understand so far. From these equations, he deduces an algorithm which performs only O(lg n) multiplications.

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 必须是到目前为止计算出的当前值。但是经过数次阅读后，我仍然不了解他从这些方程式中如何设计此算法，甚至无法理解其工作原理。谁能解释？

It appears that x must be the current value computed so far. But still after reading this several times, I don't understand how from those equations he designed this algorithm, or even how it works. Can anyone explain?

推荐答案

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

First of all, let's fix your algorithm:

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 ，当然）。

Say you want to calculate power(2,8), that is, 2^8 (^ is not XOR here, of course).

• 1）（ a = 2 ， n = 8 ）。 2 ^ 8 =（2 ^ 4）^ 2 ，所以我们必须计算 x = 2 ^ 4 ，然后然后 x * x 产生最终结果。我们必须再次调用 power（）以获得 x 。 power（2,4）。

• 1) (a=2, n=8). 2^8 = (2^4)^2, so we have to calculate x=2^4, and then x*x to yield the final result. We have to call power() again to get x. power(2,4).

2）（ a = 2 ， n = 4 ）。 2 ^ 4 =（2 ^ 2）^ 2 ，所以我们必须计算 x = 2 ^ 2 ，然后然后 x * x 产生最终结果。我们必须再次调用 power（）以获得 x 。 power（2,2）。

2) (a=2, n=4). 2^4 = (2^2)^2, so we have to calculate x=2^2, and then x*x to yield the final result. We have to call power() again to get x. power(2,2).

3）（ a = 2 ， n = 2 ）。 2 ^ 2 =（2 ^ 1）^ 2 ，所以我们必须计算 x = 2 ^ 1 ，然后然后 x * x 产生最终结果。我们必须再次调用 power（）以获得 x 。 power（2,1）。

3) (a=2, n=2). 2^2 = (2^1)^2, so we have to calculate x=2^1, and then x*x to yield the final result. We have to call power() again to get 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）。

4) (a=2, n=1). 2^1 = (2^0)^2, so we have to calculate x=2^0, and then a*x*x to yield the final result. We have to call power() again to get x. power(2,0).

5）（ a = 2 ， n = 0 ）。 2 ^ 0 = 1 因为 n 是 0 ，所以我们将值 x 返回到步骤＃4。

5) (a=2, n=0). 2^0 = 1 because n is 0, so we have the value of x that is returned to step #4.

4）（ a = 2 ， n = 1 ， x = 1 ）。此步骤的最终结果是 a * x * x = 2 * 1 * 1 = 2 ，这是要分配给 x 在步骤＃3中。

4) (a=2, n=1, x=1). The final result for this step is a*x*x = 2*1*1=2, which is the value to be assigned to x in step #3.

3）（ a = 2 ， n = 2 ， x = 2 ）。此步骤的最终结果是 x * x = 2 * 2 = 4 。这是要在步骤2中分配给 x 的结果。

3) (a=2, n=2, x=2). The final result for this step is x*x = 2*2 = 4. This is the result to be assigned to x in step #2.

2）（ a = 2 ， n = 4 ， x = 4 ）。此步骤的最终结果是 x * x = 4 * 4 = 16 。这是在步骤＃1中分配给 x 的结果。

2) (a=2, n=4, x=4). The final result for this step is x*x = 4*4 = 16. This is the result to be assigned to x in step #1.

1）（ a = 2 ， n = 8 ， x = 16 ）。此步骤的最终结果是 x * x = 16 * 16 = 256 。这是要由 power（2,8）返回的结果。

1) (a=2, n=8, x=16). The final result for this step is x*x = 16*16 = 256. This is the result to be returned by power(2,8).

这篇关于如何解释这种计算数字幂的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！