参考:数据结构与算法分析——Java语言描述
(美) Mark Allen Weiss
计算一个整数的幂
XN 的常见算法是使用 N-1 次乘法自乘。然而我们可以找到更好的算法。可以应用这样一种递归算法:如果 N 是偶数,有XN=XN/2
* X N/2 , 如果 N 是奇数,则有
XN =X (N-1)/2 * X (N-1)/2 * X 。
为了说明这个算法为什么更高效,我们举一个例子。例如计算 X62
,用第一种的常见算法我们要做61次自乘。而用第二种算法只要做9次乘法:
X3=(X2)X , X7=(X3)2X , X15=(X7)2X , X31=(X15)2X , X62=(X31)2
因为求
X3 X7 X15 X31 各做了两次乘法,最后求
X62 又做了一次乘法,总共就是9次。
代码如下:
public long pow(long x,int n){ if(n==0) return 1; else{ //判断n的奇偶 if(n%2==0) return pow(x*x, n/2); else return pow(x*x, (n-1)/2)*x; } }
由取幂运算得到的数可能会很大。我们可以使用 java 的 BigInteger 类,这个类可以用来处理任意大的整数。修改以上代码:
public BigInteger pow2(BigInteger x,int n){ if(n==0) return BigInteger.valueOf(1); else { if(n%2==0) return pow2(x.multiply(x), n/2); else return pow2(x.multiply(x), (n-1)/2).multiply(x); } }
~完~