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

Например, если вы хотите вычислить 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

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

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

power() функция для работы на Integers Only

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

}

Complexity = 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 
    }

} 

Complexity = O (log (exp))

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

int pow(int base, int pow) {
  int res = 1;
  for(int i=pow; i<pow; i++)
    res *= base;

  return res;
}

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

который вызывает неопределенное поведение при реализации с целыми числами со знаком, и неправильные значения для высокого ввода при реализации с целыми числами без знака,

здесь - модифицированная версия Exponentiation by Squaring, которая также работает со знаковыми целочисленными типами и не дает неправильных значений:

#include <stdint.h>

#define SQRT_INT64_MAX (INT64_C(0xB504F333))

int64_t alx_pow_s64 (int64_t base, uint8_t exp)
{
    int_fast64_t    base_;
    int_fast64_t    result;

    base_   = base;

    if (base_ == 1)
        return  1;
    if (!exp)
        return  1;
    if (!base_)
        return  0;

    result  = 1;
    if (exp & 1)
        result *= base_;
    exp >>= 1;
    while (exp) {
        if (base_ > SQRT_INT64_MAX)
            return  0;
        base_ *= base_;
        if (exp & 1)
            result *= base_;
        exp >>= 1;
    }

    return  result;
}

Рассмотрение этой функции:

(1 ** N) == 1
(N ** 0) == 1
(0 ** 0) == 1
(0 ** N) == 0

Если произойдет переполнение или перенос,return 0;

Я использовалint64_t, но любую ширину (со знаком или без знака) можно использовать с небольшими изменениями. Однако, если вам нужно использовать целочисленный тип без фиксированной ширины, вам нужно изменитьSQRT_INT64_MAX по(int)sqrt(INT_MAX) (в случае использованияint) или что-то подобное, что должно быть оптимизировано, но это уродливее, а не константное выражение C. Также приведение результатаsqrt() дляint не очень хорош из-за точности с плавающей запятой в случае идеального квадрата, но я не знаю ни одной реализации, гдеINT_MAX - или максимум любого типа - это идеальный квадрат, вы можете жить с этим.

когда вам нужно сказать 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 плавает, другие особые случаи возведения в степень могут представиться.

если exp четен, 5 ^ 10 = 25 ^ 5.

int pow(float base,float exp){
   if (exp==0)return 1;
   else if(exp>0&&exp%2==0){
      return pow(base*base,exp/2);
   }else if (exp>0&&exp%2!=0){
      return base*pow(base,exp-1);
   }
}

который запоминает все вычисленные мощности, а затем использует их при необходимости. Так, например, x ^ 13 равно (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, где x ^ 2 ^ 2 это взято из таблицы вместо того, чтобы вычислять это снова. Количество необходимых умножений: Ceil (Log n)

public static int Power(int base, int exp)
{
    int tab[] = new int[exp + 1];
    tab[0] = 1;
    tab[1] = base;
    return Power(base, exp, tab);
}

public static int Power(int base, int exp, int tab[])
    {
         if(exp == 0) return 1;
         if(exp == 1) return base;
         int i = 1;
         while(i < exp/2)
         {  
            if(tab[2 * i] <= 0)
                tab[2 * i] = tab[i] * tab[i];
            i = i << 1;
          }
    if(exp <=  i)
        return tab[i];
     else return tab[i] * Power(base, exp - i, tab);
}

вы можете использовать шаблоны, чтобы развернуть цикл. Это можно сделать более эффективным, но я хотел продемонстрировать здесь основной принцип:

#include <iostream>

template<unsigned long N>
unsigned long inline exp_unroll(unsigned base) {
    return base * exp_unroll<N-1>(base);
}

Мы завершаем рекурсию, используя специализацию шаблона:

template<>
unsigned long inline exp_unroll<1>(unsigned base) {
    return base;
}

Показатель степени должен быть известен во время выполнения,

int main(int argc, char * argv[]) {
    std::cout << argv[1] <<"**5= " << exp_unroll<5>(atoi(argv[1])) << ;std::endl;
}

- сдвинуться силой.

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

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);
}

Вот метод в 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;
}

возведенное в степень чего-либо, всегда лучше использовать параметр сдвига:

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

Это намного эффективнее.

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

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

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

Редактировать

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

более общее решение с учетом отрицательного показателя

private static int pow(int base, int exponent) {

    int result = 1;
    if (exponent == 0)
        return result; // base case;

    if (exponent < 0)
        return 1 / pow(base, -exponent);
    int temp = pow(base, exponent / 2);
    if (exponent % 2 == 0)
        return temp * temp;
    else
        return (base * temp * temp);
}

я пытаюсь создать маску из власти, но я решил поделиться найденным решением.

Очевидно, это работает только для степеней 2.

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;

Below - это решение, которое также работает сy < 0 как можно лучше.

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.

это не самое эффективное решение, но число итераций такое же, как у экспоненциального решения.

public static long pow(long base, long exp){        
    if(exp ==0){
        return 1;
    }
    if(exp ==1){
        return base;
    }

    if(exp % 2 == 0){
        long half = pow(base, exp/2);
        return half * half;
    }else{
        long half = pow(base, (exp -1)/2);
        return base * half * half;
    }       
}