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

Question

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

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

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

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

Answer 2

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

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

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

Answer 3

Я реализовал алгоритм, который запоминает все вычисленные мощности, а затем использует их при необходимости. Так, например, x ^ 13 равно (x ^ 2) ^ 2 ^ 2 * x ^ 2 ^ 2 * x, где x ^ 2 ^ 2 это взято из таблицы вместо того, чтобы вычислять это снова Это в основном реализация ответа @Pramod (но в C #). Количество необходимых умножений: 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);
}

Answer 4

Я использую рекурсивный, если 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);
   }
}

Answer 5

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

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

Answer 6

Еще одна реализация (на Java). Может быть не самое эффективное решение, но число итераций такое же, как у экспоненциального решения.

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

Answer 7

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

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

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

Answer 8

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

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

  return res;
}

РЕДАКТИРОВАТЬ: Как уже указывалось, это не самый эффективный способ ... до тех пор, пока вы определяете эффективность как циклы процессора, что, я думаю, достаточно справедливо.