13

所以我参加了一次工作面试，他们让我在白板上写下一个快速的数学幂方法，这就是我放在那里的

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 的幂？有任何想法吗？

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

4

3 回答 3

20

http://en.wikipedia.org/wiki/Exponentiation_by_squaring “基本方法”是 O(log n)，而不是这个 O(n) 算法。（番石榴有一个非递归的实现。）

此外，您的功率参数几乎可以肯定是int. （如果你真的想实现一个算法来将数字提升到非整数幂，你将需要更多的数学运算。）

于 2013-04-23T23:38:40.713 回答
2

跳出框框思考一下，通常在内存和速度之间进行权衡。有记忆的概念。

您可以添加一个静态 double[][] 缓存来存储任何特定值的结果。

就像是：

// 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
}

这会起作用，但会占用大量内存。

于 2013-04-24T00:39:05.927 回答
0

将答案与自身和其他确定的倍数相乘可以为您带来不同的权力，这可以让您更快地接近解决方案。Louis 提供的 wiki 很好。如果您想要一个通用的解释，请考虑：

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

上面的例子是为了表明你不必只玩方块。如果你玩这个，使用各种幂，你会发现有时你可以做得比只使用 2 的幂...这是一个有趣的数学问题。

于 2013-04-24T00:29:11.827 回答