快速求幂算法Java实现
文章目录
快速求幂算法inJava
一、累乘
最傻的办法也是最容易理解的，
时间复杂度 O(n)
public static double power(double base,int exponent){
double d =1;
while(exponent > 0){
d *= base;
exponent--;
}
return d;
}
我们根据这个算法，推演 15^9 的运算过程
| 变量名 | 初始 | 循环 1次 | 循环 2次 | 循环 3次 | ··· ··· | 循环 9次 |
|---|---|---|---|---|---|---|
| d | 1 | 15 | 15^2 | 15^3 | ··· ··· | 15^9 |
| base | 15 | 15 | 15 | 15 | ··· ··· | 15 |
| exponent | 9 | 8 | 7 | 6 | ··· ··· | 0 |
幂的定义本身就是累乘，求多少次幂就要累乘多少次，显然这个算法是低效的，base变量没有充分利用起来，唯一的好处就是很好理解。
二、化繁为简求幂
用递归的思想 拆解大数为小数 (此处是把小幂化大幂)
时间复杂度 O(logn)
public static double Power0(double base, int exponent) {
double d = 1;
while(exponent > 0){
if(exponent % 2 == 1){
d *= base;
}
base *= base;
exponent >>= 1;
}//while
return d;
}
我们根据这个算法，推演 15^9 的运算过程
| 变量名 | 初始 | 循环 1次 | 循环 2次 | 循环 3次 | 循环 4次 |
|---|---|---|---|---|---|
| if 成立 | √ | √ | |||
| d | 1 | 15 | 15 | 15 | 15^9 |
| base | 15 | 15^2 | 15^4 | 15^8 | 15^16 |
| exponent | 9 | 4 | 2 | 1 | 0 |
时间复杂度 O(logn)，这个算法并不是做乘法数最少的，但多数情况下是足够快并且足够简单的。如果单纯追求做乘法数最少，则不应用2^k次幂进行计算，我们可以选取更高次的幂来进行，比如(exp%8)、(exp%4)等等。
当然我们也可以用递归的形式来解决，但是其逻辑上是相近的，是只形式不一样。
实际上该运算会引起精度问题，并且无法避免:
(我们可以通过增加变量if(i==9)，来控制最后一次 base * base大数相乘)
然后我们进一步，
考虑负指数
我们完善一下，考虑负指数的情况。同时，对指数为0的情况进行处理。(不考虑底数为0)
public static double Power(double base, int exponent) {
double d = 1;//default = 1; if exp == 0 ,deturn 1;
boolean flag = true;
if(exponent != 0){
if(exponent < 0){
exponent = Math.abs(exponent);
flag = false;
}
while(exponent > 0){
if(exponent % 2 == 1){
d *= base;
}
base *= base;
exponent >>= 1;
}
}//
if(flag) {
return d;
}else {
return 1/d;
}
}
引入（import） java.lang.Math中的取绝对值函数。
实际上，出现负指数是我们只需对其求倒数即可。
end:
最后我们欣赏一下，java.lang.Math中的power函数：
好吧是个native方法，谁有native源码给大家分享一下
参考：