我的Java幂法的效率？

Question

于是我参加了一次求职面试，他们让我在白板上写一个快速的数学能力方法，这就是我放在那里的。

public static double pow(double base, double power) {
    double result = 1.0;
    for(double x = 0; x < power; x++) {
        result = result * base;
    }

    return result;
}

这起了作用，他们对此很满意，但接着又问我怎样才能使它更有效率，但我没有得到任何答复。所以我的问题是，你能比这个更有效率吗?或者这仅仅是一个让我流汗的问题？我在想，可能有一些直接的位移位解决方案，但我不完全确定，我认为这将只适用于2的幂？有什么想法吗？

*编辑对不起--我忘了提到方法签名是给我的(双数作为输入)，我被告知不能使用任何内置的数学库。

Answer 1

平方的“基本方法”是O(log )，而不是这个O(n)算法。(番石榴有一个非递归实现。)

而且，您的power参数几乎肯定是一个int。(如果你真的想实现一个将数字提高到非整数幂的算法，你将需要更多的数学。)

Answer 2

从思维的角度来看，在记忆和速度之间通常会有一种权衡。有回忆录的概念。

您可以添加一个静态双缓存，用于存储任何特定值的结果。

类似于：

// look for the value in the cache, if it is there return it.

for(double x = 0; x < power; x++) {
    result = result * base;
    // store result in the cache
}

这是可行的，但需要大量的内存。

Answer 3

将答案与自身和其他决定性倍数相乘可以产生不同的力量，这可以使你更快地接近解决方案。维基路易提供的是好的。如果您想要一个通用的解释，请考虑：

2^1 * 2^1 = 2^2
2^2 * 2^2 = 2^4
2^4 * 2^4 = 2^8
...

这对两个人的力量非常有用。然而，我发现和两个人的非力量一起玩很有趣。所以，如果我想要2^13，我怎么能做到呢？

2^1 * 2^1 = 2^2
2^1 * 2^2 = 2^3
2^3 * 2^3 = 2^6
2^6 * 2^6 = 2^12
2^12 * 2^1 = 2^13

上面的例子是为了说明你不必只玩正方形游戏。如果你玩这个这是个有趣的数学题。