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

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

<code>// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125
</code>
 Andy Lester02 окт. 2008 г., 19:26
Когда вы говорите «эффективность», вам нужно указать «эффективность» в отношении чего. Скорость? Использование памяти? Размер кода? Ремонтопригодность?
 EsmaeelE29 окт. 2017 г., 16:42
pow() небезопасная функция
 Adrian McCarthy07 янв. 2016 г., 18:15
Если ты придерживаешься фактическогоints (а не какой-то класс огромный-int), многие вызовы ipow будут переполнены. Это заставляет меня задуматься, есть ли умный способ предварительно рассчитать таблицу и свести все непересекающиеся комбинации к простому поиску в таблице. Это займет больше памяти, чем большинство общих ответов, но, возможно, будет более эффективным с точки зрения скорости.
 Nathan Fellman30 мая 2009 г., 15:46
да, но это работает на числах с плавающей или двойной, а не на целых
 jalf30 мая 2009 г., 15:07
Разве в C нет функции pow ()?

Ответы на вопрос(18)

Решение Вопроса

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

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

    return result;
}

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

 orlp31 авг. 2012 г., 13:18
Я написал более оптимизированную версию, которую можно бесплатно скачать здесь: Gist.github.com / 3551590 На моей машине это было примерно в 2,5 раза быстрее.
 user987628 июл. 2009 г., 18:42
Вы, вероятно, должны добавить проверку, что "exp" не является отрицательным. В настоящее время эта функция либо даст неправильный ответ, либо зациклится навсегда. (В зависимости от того, выполняет ли >> = для целого со знаком int заполнение нулями или расширение знака - компиляторы C могут выбирать любое поведение).
 Craig McQueen21 авг. 2013 г., 02:40
Ваша функция, вероятно, должна иметьunsigned exp, или же обработать отрицательныйexp должным образом
 Ilmari Karonen08 апр. 2013 г., 18:38
@ AkhilJain: Это очень хорошо, С; чтобы сделать его действительным и в Java, заменитеwhile (exp) а такжеif (exp & 1) сwhile (exp != 0) а такжеif ((exp & 1) != 0) соответственно.
 bames5312 окт. 2015 г., 00:40
@ 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, только с тремя умножениями. При больших показателях разница в производительности значительна.

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

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

 Josiah Yoder17 авг. 2018 г., 21:25
Это может быть оптимизировано для целых чисел, потому что есть целых 255 целочисленных степеней, которые не вызовут переполнение для 32-битных целых Вы можете кэшировать оптимальную структуру умножения для каждого типа int. Я представляю, что код + данные все равно будут меньше, чем простое кэширование всех полномочий ...
 Eric Postpischil27 дек. 2013 г., 22:32
@ JeremySalwen: Как говорится в этом ответе, двоичное возведение в степень не является вообще самым оптимальным методом. В настоящее время не существует эффективных алгоритмов для нахождения минимальной последовательности умножений.
 Pacerier16 сент. 2014 г., 11:03
@ EricPostpischil, это зависит от вашего приложения. Обычно нам не нуженгенеральны алгоритм работы длявс цифры. См. Искусство компьютерного программирования, том. 2: Получисленные алгоритмы
 Toby Speight19 окт. 2015 г., 12:03
Вот эта точная проблема в От математики к общему программированию Александр Степанов и Даниэль Роуз. Эта книга должна быть на полке у каждого специалиста по программному обеспечению, ИМХО.
 lhf14 апр. 2016 г., 13:27
Смотрите также En.wikipedia.org / вики / ....

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

 Cacahuete Frito17 мар. 2019 г., 19:17
научной библиотеки ГНУ уже есть ваша вторая функция: Gnu.org / Программное обеспечение / GSL / ручной / html_node / Small-целочисленного powers.html
 greybeard07 янв. 2016 г., 21:27
Как это отличается от ответовAbhijit Gaikwad а также Chux? Пожалуйста, аргументируйте использованиеfloat во втором представленном блоке кода (рассмотрим, какpower(2.0, -3) вычисляется).
 roottraveller08 янв. 2016 г., 04:34
@ greybeard Я упомянул некоторые комментарии. может быть, что может решить ваш запрос

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

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

  return res;
}

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

 Greg Rogers11 окт. 2008 г., 15:54
Этот код не работает как написано, я должен быть инициализирован 0, а не пау. @ paperhorse, N - это pow, то есть от 0 до INT_MAX.
 Akhil Jain16 дек. 2012 г., 06:55
Я = ПР; г <ПР; я ++,i уже переведено наpow и затем итерация кpow, цикл будет выполняться только один раз, вы должны уменьшить i. не так ли?
 MSalters19 сент. 2008 г., 15:06
O (N) где O (log N) возможно - см. Yarrkov
 paperhorse28 сент. 2008 г., 00:01
Это может быть самым эффективным. N не может быть сколь угодно большим. Его максимум составляет 31 или 63 (в зависимости от вашего размера int). Это похоже на то, как сортировка вставки превосходит быструю сортировку для низкого
 MSalters13 авг. 2015 г., 11:40
@ paperhorse: На самом делеpow(1, INT_MAX) четко определен.

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

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

 Drealmer19 сент. 2008 г., 14:55
* = тоже не сработает, показатель степени может быть нулевым
 paxdiablo19 сент. 2008 г., 14:37
Отличное решение, но без тени ??
 Drealmer19 сент. 2008 г., 14:50
IEEE float - это базовая x 2 ^ exp, изменение значения экспоненты не приведет ни к чему, кроме умножения на степень два, и велики шансы, что оно денормализует число с плавающей точкой ... ваше решение неверно IMHO
 Doug T.19 сент. 2008 г., 14:39
Да, мой плохой. :) спасибо за указание на это.
 Drealmer19 сент. 2008 г., 15:02
База 10? Ну нет, это база 2, если вы не имели в виду 10 в двоичном:)

если 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);
}
 Cacahuete Frito17 мар. 2019 г., 20:33
public? 2 функции названы одинаково? Это вопрос

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

#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;
}
 Cacahuete Frito17 мар. 2019 г., 17:05
Это явно не вопрос C ++.(c != c++) == 1

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

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)
 Jake30 дек. 2011 г., 19:22
2 ** 0 == 1 << 0 == 1
 Rob Smallshire23 нояб. 2011 г., 22:39
Есть ли элегантный способ сделать это так, чтобы 2 ** 0 == 1?
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);
}
 bartgol15 авг. 2017 г., 17:15
Единственный отрицательный показатель, которыйможе не заставляет вас выходить из диапазона int -1. И это работает только если база 1 или -1. Таким образом, есть только две пары (base, exp) с exp <0, которые не приводят к нецелым степеням. Хотя я математик и мне нравятся квантификаторы, я думаю, что в этом случае на практике можно сказать, что отрицательный показатель заставляет вас покинуть целочисленную область ...
 MSalters13 авг. 2015 г., 11:34
Не мой голос, ноpow(1, -1) не покидает диапазон int, несмотря на отрицательный показатель. Теперь это работает случайно, как иpow(-1, -1).

Вот метод в 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;
}
 Cacahuete Frito17 мар. 2019 г., 19:47
Это НЕ вопрос Java!
 Anushree Acharjee10 июл. 2015 г., 07:26
не работает для больших онемений, например, Pow (71045970,41535484)
 Raman Yelianevich24 нояб. 2015 г., 19:15
Используйте BigInteger # modPow или Biginteger # pow для больших чисел, соответствующие алгоритмы, основанные на размере аргументов, уже реализованы
 David Etler04 сент. 2015 г., 23:13
@ AnushreeAcharjee конечно нет. Вычисление такого числа потребовало бы арифметики произвольной точности.

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

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

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

 Pavan06 июн. 2017 г., 16:18
ya но он работает только на 2 или кратных 2.

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

Преимущество такого подхода заключается в том, что он выполняется за время 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);
}
 MSalters13 авг. 2015 г., 11:38
@ chux: это может отформатировать ваш жесткий диск: целочисленное переполнение - UB.
 jswolf1929 авг. 2014 г., 17:51
езультатом деления @integer является целое число, поэтому ваш отрицательный показатель может быть намного эффективнее, поскольку он будет возвращать только 0, 1 или -1 ...
 chux01 апр. 2015 г., 18:48
pow(i, INT_MIN) может быть бесконечным циклом.
 chux13 авг. 2015 г., 16:24
@ MSalterspow(i, INT_MIN) не является целочисленным переполнением. Присвоение этого результатаtemp, безусловно, может переполниться, что может привести кконец времен, но я согласен на случайное значение. : -)

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

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

Mask1 = 1 << (Exponent - 1);
Mask2 = Mask1 - 1;
return Mask1 + Mask2;
 Michaël Roy16 июн. 2017 г., 19:06
Это было за 1 << 64? Это переполнение. Наибольшее целое число чуть ниже: (1 << 64) - 1.
 Michaël Roy15 июн. 2017 г., 18:34
Это немного надумано .... почему бы не привести = (1 << Exponent) - 1; ?
 MarcusJ16 июн. 2017 г., 19:04
Я пытался это сделать, он не работает для 64-битной версии, он никогда не возвращается, и в этом конкретном случае я пытаюсь установить все биты ниже X включительно.
 Michaël Roy16 июн. 2017 г., 19:18
1 << 64 == 0, вот почему. Может быть, ваше представление лучше всего подходит для вашего приложения. Я предпочитаю вещи, которые можно поместить в макрос, без дополнительной переменной, например,#define MASK(e) (((e) >= 64) ? -1 :( (1 << (e)) - 1)), так что это может быть вычислено во время компиляции
 MarcusJ18 июн. 2017 г., 01:11
Да, я знаю, что такое переполнение. Только то, что я не использовал это слово, не является приглашением к ненужной снисходительности. Как я уже сказал, это работает для меня, и потребовалось немало усилий, чтобы узнать, а потом поделиться им. Это так просто

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

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

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.

 Cacahuete Frito17 мар. 2019 г., 19:00
powjii(INT_MAX, 63) вызывает UB вbase *= base. Подумайте о том, чтобы проверить, что вы можете умножить или перейти к неподписанному и позволить ему обернутьс
 Cacahuete Frito17 мар. 2019 г., 20:38
Нет причин иметьexp быть подписанным. Это усложняет код из-за странной ситуации, когда(-1) ** (-N) действителен, и любойabs(base) > 1 будет0 для отрицательных значенийexp, так что лучше оставить его без знака и сохранить этот код.
 chux18 мар. 2019 г., 00:01
@ CacahueteFrito Правда, чтоy как подпись на самом деле не нужна и приносит сложности, которые вы прокомментировали, но запрос OP был специфическимpow(int, int). Таким образом, эти хорошие комментарии относятся к вопросу ОП. Поскольку OP не указал, что делать при переполнении, четко определенный неправильный ответ лишь немного лучше, чем UB. Учитывая "самый эффективный способ", я сомневаюсь, что OP заботится о OF.

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

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;
    }       
}
 Cacahuete Frito17 мар. 2019 г., 19:47
Не вопрос Java!

Ваш ответ на вопрос