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

249

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

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

// 5^5
pow(5,5) == 3125
Дуг Т.
источник
3
Когда вы говорите «эффективность», вам нужно указать эффективность в отношении чего. Скорость? Использование памяти? Размер кода? Ремонтопригодность?
Энди Лестер
Разве в C нет функции pow ()?
Половина
16
да, но это работает на числах с плавающей или двойной, а не на целых числах
Натан Феллман
1
Если вы придерживаетесь фактического ints (а не какого-то класса large-int), многие вызовы ipow будут переполнены. Это заставляет меня задуматься, есть ли умный способ предварительно рассчитать таблицу и свести все непересекающиеся комбинации к простому поиску в таблице. Это займет больше памяти, чем большинство общих ответов, но, возможно, будет более эффективным с точки зрения скорости.
Адриан Маккарти
pow()не безопасная функция
EsmaeelE

Ответы:

391

Возведение в степень путем возведения в квадрат.

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

    return result;
}

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

Элиас Яррков
источник
38
Вы, вероятно, должны добавить проверку, что «exp» не является отрицательным. В настоящее время эта функция будет либо давать неправильный ответ, либо зацикливаться навсегда. (В зависимости от того, выполняет ли >> = для целого со знаком int заполнение нулями или расширение знака - компиляторы C могут выбирать любое поведение).
user9876
23
Я написал более оптимизированную версию, которую можно бесплатно загрузить здесь: gist.github.com/3551590 На моей машине она была примерно в 2,5 раза быстрее.
orlp
10
@AkhilJain: Это очень хорошо, С; чтобы сделать его действительным также в Java, замените while (exp)и if (exp & 1)на while (exp != 0)и if ((exp & 1) != 0)соответственно.
Ильмари Каронен,
3
Ваша функция, вероятно, должна иметь unsigned exp, или иначе обрабатывать негатив expправильно.
Крейг МакКуин
5
@ZinanXing Умножение n раз приводит к большему умножению и медленнее. Этот метод экономит умножения, эффективно используя их. Например, для вычисления n ^ 8 наивный метод n*n*n*n*n*n*n*nиспользует 7 умножений. Этот алгоритм вместо этого вычисляет m=n*n, а o=m*mзатем p=o*o, где p= n ^ 8, только с тремя умножениями. При больших показателях разница в производительности значительна.
bames53
69

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

Например, если вы хотите вычислить 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⁶ должна быть вычислена как (a³) ², так как a³ используется повторно (в отличие, скажем, от a⁶ = a² (a²) ², что также требует трех умножений ).

Pramod
источник
4
@JeremySalwen: Как говорится в этом ответе, двоичное возведение в степень не является в целом наиболее оптимальным методом. В настоящее время не существует эффективных алгоритмов для нахождения минимальной последовательности умножений.
Эрик Постпищил
2
@EricPostpischil, это зависит от вашего приложения. Обычно нам не нужен общий алгоритм для работы со всеми числами. См. Искусство компьютерного программирования, том. 2:
Полу численные
3
Точную проблему можно найти в статье « От математики к общему программированию » Александра Степанова и Даниэля Роуза. Эта книга должна быть на полке у каждого специалиста по программному обеспечению, ИМХО.
Тоби Спейт
2
Смотрите также en.wikipedia.org/wiki/… .
LHF
Это может быть оптимизировано для целых чисел, поскольку существует целых 255 целочисленных степеней, которые не вызовут переполнения для 32-битных целых чисел. Вы можете кэшировать оптимальную структуру умножения для каждого целого. Я представляю, что код + данные все равно будут меньше, чем простое кэширование всех полномочий ...
Джозия Йодер
22

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

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
Джейк
источник
Есть ли элегантный способ сделать это так, чтобы 2 ** 0 == 1?
Роб Смолшир,
16
2 ** 0 == 1 << 0 == 1
Джейк
14

Вот метод в 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;
}
user1067920
источник
не работает для больших онемений, например, Pow (71045970,41535484)
Anushree Acharjee
16
@AnushreeAcharjee конечно нет. Вычисление такого числа потребовало бы арифметики произвольной точности.
Дэвид Этлер
Используйте BigInteger # modPow или Biginteger # pow для больших чисел, соответствующие алгоритмы, основанные на размере аргументов, уже реализованы
Раман Елианевич
Это НЕ вопрос Java!
Cacahuete Frito
7
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);
}
Крис Кадмор
источник
Не мой голос, но pow(1, -1)не покидает диапазон int, несмотря на отрицательный показатель. Теперь это работает случайно, как и pow(-1, -1).
MSalters
Единственный отрицательный показатель, который не может заставить вас покинуть диапазон int, равен -1. И это работает только если база равна 1 или -1. Таким образом, есть только две пары (base, exp) с exp <0, которые не приводят к нецелым степеням. Хотя я математик и мне нравятся квантификаторы, я думаю, что в этом случае на практике можно сказать, что отрицательный показатель заставляет вас покинуть целочисленную область ...
bartgol
6

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

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

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

адитйа
источник
6

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

roottraveller
источник
Чем это отличается от ответов Abhijit Gaikwad и Chux ? Пожалуйста, аргументируйте использование floatво втором представленном блоке кода (рассмотрите возможность показа power(2.0, -3)вычислений).
седобородый
@greybeard Я упомянул некоторые комментарии. может быть, что может решить ваш запрос
roottraveller
1
GNU Scientific Library уже имеет свою вторую функцию: gnu.org/software/gsl/manual/html_node/Small-integer-powers.html
Cacahuete Frito
@roottraveller не могли бы вы объяснить negative exp and float baseрешение? почему мы используем temp, разделяем exp на 2 и проверяем exp (четное / нечетное)? Спасибо!
Лев
6

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

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

Дуг Т.
источник
Отличное решение, но unigend ??
paxdiablo
IEEE с плавающей запятой имеет базовое значение x 2 ^ exp, изменение значения экспоненты не приведет ни к чему, кроме умножения на степень два, и велики шансы, что оно денормализует число с плавающей запятой ... Ваше решение неверно ИМХО
Drealmer
Вы все правы, я неправильно запомнил, что мое решение изначально было написано, о, так давно, для степеней 2 явно. Я переписал свой ответ, чтобы решить проблему в особом случае.
Даг Т.
Во-первых, код разбит на кавычки и требует редактирования для его компиляции. Во-вторых, код нарушен на core2d с использованием gcc. увидеть этот дамп Возможно, я сделал что-то не так. Однако я не думаю, что это сработает, поскольку показатель IEEE с плавающей запятой равен основанию 10.
свободное пространство
3
База 10? Ох, нет, это база 2, если вы не имели в виду 10 в двоичном коде :)
Drealmer
4

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

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

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

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

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

Джейсон З
источник
2

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

Ниже приведено решение, которое также работает 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.

Chux - Восстановить Монику
источник
powjii(INT_MAX, 63)вызывает UB в base *= base. Подумайте о том, чтобы проверить, что вы можете умножить или перейти к неподписанному и позволить ему обернуться.
Cacahuete Frito
Нет никаких оснований expбыть подписанным. Это усложняет код из-за нечетной ситуации, где (-1) ** (-N)допустимо, и любая abs(base) > 1будет 0для отрицательных значений exp, поэтому лучше оставить его без знака и сохранить этот код.
Cacahuete Frito
1
@CacahueteFrito Правда, yпоскольку подписанный документ на самом деле не нужен и приносит сложности, которые вы прокомментировали, тем не менее, запрос OP был конкретным pow(int, int). Таким образом, эти хорошие комментарии относятся к вопросу ОП. Так как OP не указал, что делать при переполнении, четко определенный неправильный ответ лишь немного лучше, чем UB. Учитывая "наиболее эффективный способ", я сомневаюсь, что OP заботится о OF.
chux - Восстановить Монику
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);
}
Абхиджит Гайквад
источник
1
целочисленное деление приводит к целому числу, поэтому ваш отрицательный показатель может быть намного эффективнее, поскольку он будет возвращать только 0, 1 или -1 ...
jswolf19
pow(i, INT_MIN)может быть бесконечный цикл.
chux - Восстановить Монику
1
@chux: это может отформатировать ваш жесткий диск: целочисленное переполнение - UB.
MSalters
@MSalters pow(i, INT_MIN)не является целочисленным переполнением. Назначение этого результата, tempбезусловно, может быть переполнено, что может привести к концу времени , но я согласен на случайное значение. :-)
chux - Восстановить Монику
0

Еще одна реализация (на 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;
    }       
}
Вайбхав Фоуздар
источник
Не вопрос Java!
Cacahuete Frito
0

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

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

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

Какауэте Фрито
источник
0

Я реализовал алгоритм, который запоминает все вычисленные мощности, а затем использует их при необходимости. Так, например, 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);
}
Rank1
источник
public? 2 функции названы одинаково? Это вопрос C.
Cacahuete Frito
-1

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

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

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
MarcusJ
источник
Я попробовал это, он не работает для 64 бит, он сдвинут, чтобы никогда не возвращаться, и в этом конкретном случае я пытаюсь установить все биты ниже X включительно.
MarcusJ
Это было для 1 << 64? Это переполнение. Наибольшее целое число чуть ниже: (1 << 64) - 1.
Микаэль Рой
1 << 64 == 0, вот почему. Может быть, ваше представление лучше всего подходит для вашего приложения. Я предпочитаю вещи, которые можно поместить в макрос, без дополнительной переменной, например #define MASK(e) (((e) >= 64) ? -1 :( (1 << (e)) - 1)), так, чтобы они могли быть вычислены во время компиляции
Микаэль Рой
Да, я знаю, что такое переполнение. Только то, что я не использовал это слово, не является приглашением быть излишне снисходительным. Как я уже сказал, это работает для меня, и потребовалось немало усилий, чтобы узнать и поделиться им. Это так просто.
MarcusJ
Извини если я тебя обидела. Я действительно не хотел.
Микаэль Рой
-1

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

#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;
}
Йоханнес Бляшке
источник
1
Это явно не вопрос C ++. (c != c++) == 1
Cacahuete Frito