乘方函数还有简解么 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

乘方函数还有简解么

乘方函数还有简解么# JobHunting - 待字闺中

y*m2011-07-14 07:07

1 楼

一个java稍微优化的,请指点更优化解,thx!
public static double pow(double a, int b) {
if (b == 0)
return 1;
else if (b == 1)
return a;
else if (b == -1)
return a;
else if (b == 1)
return 1 / a;
else if (b == 2)
return a * a;
else if (b == -2)
return 1 / (a * a);
else if (b % 2 == 0) {
return pow(pow(a, b/2), 2);
} else {
return pow(a, b-1) * a;
}
}

i*e2011-07-14 07:07

2 楼

base case 处理 b == 0 和 b < 0 就可以了。
b == 1 和 b == 2 都不用处理。
另一个优化就是 b%2 == 0 的时候，你的函数叫了 pow() 两次。
其实叫一次就可以了。
temp = pow(a, b/2);
return temp * temp;
还有另一个优化就是改为非递归。非递归程序写起来很简洁，但是要理解为什么 work
不那么 trivial. 你可以尝试自己研究看看，不懂再来这里问。
http://stackoverflow.com/questions/101439/the-most-efficient-wa

y*m2011-07-14 07:07

3 楼

处理 -1 就行了吧
这样省了些代码，但b=1时多执行了 1/2的取整操作，b=2时多执行了2-3步代码吧...
nod
public static double pow(double a, int b) {
if (b == 0)
return 1;
else if (b == -1)
return 1/a;
else if (b == 1)
return a;
else if (b == 2)
return a*a;
else if (b == -2)
return 1/(a*a);
else if (b % 2 == 0) {
double tmp = pow(a, b/2);
return tmp*tmp;
} else
return pow(a, b-1) * a;
}
work
这个怎么转换java? 可以支持 double么？
thx!

【在 i**********e 的大作中提到】

: base case 处理 b == 0 和 b < 0 就可以了。
: b == 1 和 b == 2 都不用处理。
: 另一个优化就是 b%2 == 0 的时候，你的函数叫了 pow() 两次。
: 其实叫一次就可以了。
: temp = pow(a, b/2);
: return temp * temp;
: 还有另一个优化就是改为非递归。非递归程序写起来很简洁，但是要理解为什么 work
: 不那么 trivial. 你可以尝试自己研究看看，不懂再来这里问。
: http://stackoverflow.com/questions/101439/the-most-efficient-wa

i*e2011-07-14 07:07

4 楼

处理 -1 而已不行，万一 -2,-3 的话会死循环。
还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
evaluation）
if (b < 0)
return 1.0/power(a, -b);
无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化
。电脑一秒可以执行上千万个操作，这省了2-3步代码也不会跟着 a 和 b 有更大的改
变。再说，每次递归都要试探好多 if 语句，耗费没必要的 cpu。（你的代码 base
case 好像也写错了）。
java 我不懂，但跟 C++ 挺像的，也支持 bit 操作，除了 >>= 是 logical right
shift 之外（C++ 的是 arithmetic right shift)，其他应该是一样的吧。所以
stackoverflow 贴的代码应该直接 java 就可以编译。我不是 java 的 master，所以
错了请纠正。

【在 y***m 的大作中提到】

:
: 处理 -1 就行了吧
: 这样省了些代码，但b=1时多执行了 1/2的取整操作，b=2时多执行了2-3步代码吧...
: nod
: public static double pow(double a, int b) {
: if (b == 0)
: return 1;
: else if (b == -1)
: return 1/a;
: else if (b == 1)

y*m2011-07-14 07:07

5 楼

处理 -1 而已不行，万一 -2,-3 的话会死循环。
>>>java没问题..
还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
>>>java没问题...
这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
evaluation）
if (b < 0)
return 1.0/power(a, -b);
无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化
。电脑一秒可以执行上千万个操作，这省了2-3步代码也不会跟着 a 和 b 有更大的改
变。再说，每次递归都要试探好多 if 语句，耗费没必要的 cpu。
>>>en, maybe..
（你的代码 base case 好像也写错了）。
>>> 是?
java 我不懂，但跟 C++ 挺像的，也支持 bit 操作，除了 >>= 是 logical right
shift 之外（C++ 的是 arithmetic right shift)，其他应该是一样的吧。所以
stackoverflow 贴的代码应该直接 java 就可以编译。我不是 java 的 master，所以
错了请纠正。
>>>while (exp) 编译不过,int不能转换 boolean
>>>用 while (exp==1) 代替但出来结果不对
>>>这个位运算的能好改造成支持double的么?
thx!

【在 i**********e 的大作中提到】

: 处理 -1 而已不行，万一 -2,-3 的话会死循环。
: 还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
: 这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
: evaluation）
: if (b < 0)
: return 1.0/power(a, -b);
: 无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化
: 。电脑一秒可以执行上千万个操作，这省了2-3步代码也不会跟着 a 和 b 有更大的改
: 变。再说，每次递归都要试探好多 if 语句，耗费没必要的 cpu。（你的代码 base
: case 好像也写错了）。

i*e2011-07-14 07:07

6 楼

你的代码是不是复制黏贴错了？
else if (b == -1) return a;
这不对吧
还有为什么有两个 else if (b == 1) ?
while (exp) 改成 while (exp > 0) 就行了。
还有，那个代码是不处理 b < 0 的状况。

【在 y***m 的大作中提到】

:
: 处理 -1 而已不行，万一 -2,-3 的话会死循环。
: >>>java没问题..
: 还有，当 n < 0 时，n%2 是 undefined behavior 的（至少对 C++ 来讲）。
: >>>java没问题...
: 这样处理就行了：(如果放在递归函数外边会更好，每次递归避免了一个无谓的 if
: evaluation）
: if (b < 0)
: return 1.0/power(a, -b);
: 无可否认你处理 b=1 和 b=2 可以省了 2-3 步代码，但是这对电脑来说是极小的优化

y*m2011-07-14 07:07

7 楼

第二次贴改了..
然后这个 if (exp & 1) 怎么弄？改 if ((exp & 1)>0) 不行...
double怎么弄？
可以的，其实是变成了 1*a/a^(-b+1)
thx!

【在 i**********e 的大作中提到】

: 你的代码是不是复制黏贴错了？
: else if (b == -1) return a;
: 这不对吧
: 还有为什么有两个 else if (b == 1) ?
: while (exp) 改成 while (exp > 0) 就行了。
: 还有，那个代码是不处理 b < 0 的状况。

P*c2011-07-14 07:07

8 楼

我觉得你写的那个已经可以了。面试的话应该不回死抠这一个题目。如果这个题目出现
，应该是作为appetizer的形式，不会是讨论优化的重点。

【在 y***m 的大作中提到】

:
: 第二次贴改了..
: 然后这个 if (exp & 1) 怎么弄？改 if ((exp & 1)>0) 不行...
: double怎么弄？
: 可以的，其实是变成了 1*a/a^(-b+1)
: thx!