我的 Java 电源方法的效率如何？

performance math java

2022-09-04 08:30:52

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

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的幂？有什么想法吗？

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

答案 1

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

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

答案 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
}

这可以工作，但会占用大量内存。