Лучший способ сделать powerOf (int x, int n)?

Question

Итак, учитывая x и мощность n, решите для X^n. Есть простой способ, которым это O(n) ... Я могу получить его до O(n/2), выполнив

numSquares = n/2;
numOnes = n%2;
return (numSquares * x * x + numOnes * x);

Теперь есть решение O(log(n)), кто-нибудь знает, как это сделать? Это можно сделать рекурсивно.

Answer 1

Математическая концепция, которую можно использовать, состоит в том, что x<sup>2n+1</sup> = x<sup>2n</sup> &sdot; x и x<sup>2n</sup> = x<sup>n</sup> &sdot; x<sup>n</sup>.

Answer 2

Ну, вы знаете, что x ^{a + b} = x ^a x ^b , так что ...

int pow(int x, unsigned int y)
{
  if (y == 0) return 1;
  if (y == 1) return x;
  int a = y / 2;
  int xa = pow(x, a);
  if (a + a == y) // y even
    return xa * xa;
  else
    return xa * xa * x;
}

Answer 3

Обычная реализация - что-то вроде этого (взято из статьи википедии ):

long power(long x, unsigned long n)
{
    long result = 1;
    while (n > 0) {
        /* n is odd, bitwise test */ 
        if (n & 1) {
            result *= x;
        }
        x *= x;
        n /= 2;     /* integer division, rounds down */
    }
    return result;
}

Рекурсия не нужна или (я бы сказал) особенно желательна, хотя она может выиграть при очевидности:

long power(long x, unsigned long n)
{
    if (n == 0) return 1;
    long result = power(x, n/2); // x ^ (n/2)
    result *= result;            // x ^ (n/2)*2
    if (n & 1) result *= x;      // x ^ n
    return result;
}

Конечно, в любой версии вы переполняете длинную довольно быстро. Вы можете применить те же алгоритмы к своему любимому представлению bigint, хотя любая библиотека bigint уже будет включать в себя целочисленную степенную функцию.

Обе версии указанной выше функции возвращают 1 для power(0,0). Вы можете или не можете считать это ошибкой.

Answer 4

Вы найдете объяснение здесь: Быстрое возведение в степень . Для некоторых значений n вы можете вычислить x ^ n с меньшим умножением, чем при использовании степеней двух трюков.

Answer 5

Стандартный прием заключается в генерации степеней x в последовательности x ² , x ⁴ , x ⁸ , x ¹⁶, x ³² , ... и включите те, которые необходимы в результате.