Эффективность моего метода мощности Java?

Итак, я отправился на собеседование, и они попросили меня написать быстрый метод математической власти на белой доске, и вот что я там положил.

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). (Guava имеет нерекурсивную реализацию.)

Кроме того, параметр мощности почти наверняка будет int. (Если вы действительно хотите реализовать алгоритм для повышения числа до нецелочисленных полномочий, вам понадобится гораздо больше математики.)

Ответ 2

Мышление вне коробки немного, обычно есть компромисс между памятью и скоростью. Существует концепция memoization.

Вы можете добавить статический двойной [] [] кеш, который сохраняет результат для любого определенного значения.

Что-то вроде:

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

Это будет работать, но будет использовать много памяти.

Ответ 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

Приведенный выше пример показывает, что вам не нужно играть только с квадратами. Если вы играете с этим некоторым, с различными полномочиями, вы обнаружите, что иногда вы можете лучше, чем просто использовать полномочия 2... его интересную математическую задачу для игры.