Наиболее эффективный способ реализации степенной функции на основе целого числа 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

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

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

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, возведенное в степень чего-либо, всегда лучше использовать опцию shift:

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

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

Answer 7

Чрезвычайно специализированный случай - это когда вам нужно, скажем, 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, используя double в качестве базового типа.(Большое спасибо комментаторам за помощь в доработке этого поста).

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

Answer 8

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

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

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

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

Думаю, мне следует уточнить, прежде чем кто-нибудь пометит меня на предмет возможного переполнения.Такой подход предполагает, что у вас есть какая-то огромная библиотека.

Answer 9

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 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.

Answer 11

более общее решение, учитывающее отрицательный показатель

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 12

Еще одна реализация (на 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 13

Я использую рекурсивный метод, если 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 14

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

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

#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) или что-то подобное, которое должно быть оптимизировано, но оно более уродливое, а не постоянное выражение на языке Си.Также приведение результата sqrt() к int это не очень хорошо из-за точности с плавающей запятой в случае идеального квадрата, но, поскольку я не знаю ни одной реализации, где INT_MAX -или максимум любого типа - это идеальный квадрат, с этим можно жить.

Answer 15

Я реализовал алгоритм, который запоминает все вычисленные мощности, а затем использует их при необходимости.Так, например, 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 16

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

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

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

Answer 17

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

#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 18

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

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

  return res;
}

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