利用逐次平方法快速求幂

利用逐次平方法可以快速求幂,这里不局限于数的幂,但以数的幂来举例说明。

要求ak,如果直接用a连乘k次,复杂度比较大。如果把k写成如下形式:

k = u0 + 2u1 + 22u2 + ... + 2rur, ui = 0 或 1.

然后制作模a的幂次表:

a1 = A0,
a2 = (a1)2 = A02 = A1,
...
a2r = (a2r-1)2 = Ar-12 = Ar.

于是ak = A0u0A1u1...Arur

注意到Ai即为Ai-1的平方,这样复杂度就降为O(log(k)),即为O(r)。以下伪码是实现逐次平方法的有效代码:
[c]
b = 1;
while k is positive do
if k is odd
then b = a*b;
a = a*a;
k shift right by 1 bit;
return b;
[/c]



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*