我目前正在阅读Skiena的“算法设计手册”。
他描述了一种计算数字幂的算法，即计算a^n。
a^n
他首先说最简单的算法就是simple a*a*a ... *a，所以我们有了总数的n-1计算。
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)乘法的算法。
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必须是到目前为止计算出的当前值。但是在阅读了几次之后，我仍然不了解他是如何根据这些方程式设计该算法的，甚至无法理解它是如何工作的。谁能解释？
x
首先，让我们修复您的算法：
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这里）。
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)。
a=2
n=8
2^8 = (2^4)^2
x=2^4
x*x
power()
power(2,4)
2）（a=2，n=4）。2^4 = (2^2)^2，因此我们必须先计算x=2^2，然后x*x得出最终结果。我们必须power()再次致电以获得x。power(2,2)。
n=4
2^4 = (2^2)^2
x=2^2
power(2,2)
3）（a=2，n=2）。2^2 = (2^1)^2，因此我们必须先计算x=2^1，然后x*x得出最终结果。我们必须power()再次致电以获得x。power(2,1)。
n=2
2^2 = (2^1)^2
x=2^1
power(2,1)
4）（a=2，n=1）。2^1 = (2^0)^2，因此我们必须先计算x=2^0，然后a*x*x得出最终结果。我们必须power()再次致电以获得x。power(2,0)。
n=1
2^1 = (2^0)^2
x=2^0
a*x*x
power(2,0)
5）（a=2，n=0）。2^0 = 1因为n是0，所以我们将其值x返回到步骤4。
n=0
2^0 = 1
n
0
4）（ ， a=2，）。n=1 x=1此步骤的最终结果是a*x*x = 2*1*1=2，这是x在步骤＃3中分配的值。
x=1
a*x*x = 2*1*1=2
3）（ ， a=2，）。n=2 x=2此步骤的最终结果是x*x = 2*2 = 4。这是要x在步骤2中分配的结果。
x=2
x*x = 2*2 = 4
2）（ ， a=2，）。n=4 x=4此步骤的最终结果是x*x = 4*4 = 16。这是要x在步骤＃1中分配的结果。
x=4
x*x = 4*4 = 16
1）（ ， a=2，）。n=8 x=16此步骤的最终结果是x*x = 16*16 = 256。这是由返回的结果power(2,8)。
x=16
x*x = 16*16 = 256
