Наиболее эффективный способ реализации целочисленной степенной функции pow (int, int)

Question

Какой самый эффективный способ поднять целое число до степени другого целого числа в C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125

Answer 1

Возведение в квадрате.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

Это стандартный метод модульного возведения в степень для огромных чисел в асимметричной криптографии.

Answer 2

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

Например, если вы хотите вычислить x ^ 15, метод возведения в степень путем возведения в квадрат даст вам:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

Это всего 6 умножений.

Оказывается, это можно сделать, используя "всего лишь" 5 умножений через возведение в цепочку сложений .

n*n = n^2
n^2*n = n^3
n^3*n^3 = n^6
n^6*n^6 = n^12
n^12*n^3 = n^15

Нет эффективных алгоритмов для нахождения этой оптимальной последовательности умножений. От Википедия :

Проблема нахождения кратчайшей цепочки сложений не может быть решена динамическим программированием, поскольку она не удовлетворяет предположению об оптимальной подструктуре. То есть недостаточно разложить мощность на меньшие степени, каждая из которых вычисляется минимально, поскольку цепочки сложения для меньших степеней могут быть связаны (для совместного использования вычислений). Например, в самой короткой цепочке сложения для a¹⁵, указанной выше, подзадача для a be должна быть вычислена как (a³) ², так как a³ используется повторно (в отличие, скажем, от a⁶ = a² (a²) ², что также требует трех умножений ).

Answer 3

Если вам нужно поднять 2 до степени. Самый быстрый способ сделать это - сдвинуть бит силой.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

Answer 4

Вот метод в Java

private int ipow(int base, int exp)
{
    int result = 1;
    while (exp != 0)
    {
        if ((exp & 1) == 1)
            result *= base;
        exp >>= 1;
        base *= base;
    }

    return result;
}

Answer 5

int pow( int base, int exponent)

{   // Does not work for negative exponents. (But that would be leaving the range of int) 
    if (exponent == 0) return 1;  // base case;
    int temp = pow(base, exponent/2);
    if (exponent % 2 == 0)
        return temp * temp; 
    else
        return (base * temp * temp);
}

Answer 6

Чрезвычайно специализированный случай, когда вам нужно сказать 2 ^ (- x к y), где x, конечно, отрицателен, а y слишком велик, чтобы смещать int Вы все еще можете делать 2 ^ x в постоянном времени, прикручивая поплавком.

struct IeeeFloat
{

    unsigned int base : 23;
    unsigned int exponent : 8;
    unsigned int signBit : 1;
};


union IeeeFloatUnion
{
    IeeeFloat brokenOut;
    float f;
};

inline float twoToThe(char exponent)
{
    // notice how the range checking is already done on the exponent var 
    static IeeeFloatUnion u;
    u.f = 2.0;
    // Change the exponent part of the float
    u.brokenOut.exponent += (exponent - 1);
    return (u.f);
}

Вы можете получить больше степеней 2, используя удвоение в качестве базового типа. (Большое спасибо комментаторам за помощь в выравнивании этого поста).

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

Answer 7

Если вы хотите получить значение целого числа для 2, возведенное в степень чего-либо, всегда лучше использовать параметр сдвига:

pow(2,5) можно заменить на 1<<5

Это гораздо эффективнее.

Answer 8

power() функция для работы только целые числа

int power(int base, unsigned int exp){

    if (exp == 0)
        return 1;
    int temp = power(base, exp/2);
    if (exp%2 == 0)
        return temp*temp;
    else
        return base*temp*temp;

}

Сложность = O (log (exp))

power() функция, работающая для отрицательного опыта и плавающей базы .

float power(float base, int exp) {

    if( exp == 0)
       return 1;
    float temp = power(base, exp/2);       
    if (exp%2 == 0)
        return temp*temp;
    else {
        if(exp > 0)
            return base*temp*temp;
        else
            return (temp*temp)/base; //negative exponent computation 
    }

} 

Сложность = O (log (exp))

Answer 9

Так же, как в продолжение комментариев об эффективности возведения в степень путем возведения в квадрат.

Преимущество этого подхода заключается в том, что он выполняется за время log (n). Например, если вы собирались вычислить что-то огромное, например, x ^ 1048575 (2 ^ 20 - 1), вам нужно пройти цикл всего 20 раз, а не 1 миллион +, используя наивный подход.

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

Edit:

Полагаю, мне следует уточнить, прежде чем кто-то пометит меня на предмет потенциального переполнения. Этот подход предполагает, что у вас есть какая-то огромная библиотека.

Answer 10

Поздно до вечеринки:

Ниже приведено решение, которое также работает с y < 0 как можно лучше.

1. Используется результат intmax_t для максимального диапазона. Там нет положения для ответов, которые не вписываются в intmax_t.
2. powjii(0, 0) --> 1, что является общим результатом для этого случая.

3. pow(0,negative), еще один неопределенный результат, возвращает INTMAX_MAX

   intmax_t powjii(int x, int y) {
     if (y < 0) {
       switch (x) {
         case 0:
           return INTMAX_MAX;
         case 1:
           return 1;
         case -1:
           return y % 2 ? -1 : 1;
       }
       return 0;
     }
     intmax_t z = 1;
     intmax_t base = x;
     for (;;) {
       if (y % 2) {
         z *= base;
       }
       y /= 2;
       if (y == 0) {
         break; 
       }
       base *= base;
     }
     return z;
   }
   

Этот код использует бесконечный цикл for(;;), чтобы избежать окончательного base *= base, общего для других зацикленных решений. Это умножение 1) не нужно и 2) может быть переполнением int*int, что является UB.