pow() реализация в cmath и эффективная замена

Question

Я читал, что cmath вычисляет pow(a,b), выполняя exp(b*log(a)). Это не должно использоваться, когда b является целым числом, поскольку оно значительно замедляет вычисления. Какие альтернативы существуют при

1. вычисления много последовательных pow() с с той же постоянной a
2. известно заранее, что b будет определенно быть целым числом?

Я ищу быстрые альтернативы, которые эффективны в этих конкретных сценариях.

Answer 1

Существует множество более быстрых альтернатив, которые я собирал в течение многих лет, которые обычно полагаются на реализацию функции recursive, и сдвиги бит для обработки умножения, когда это оправдано. Ниже приведены функции, адаптированные к integer, float и double. Они поставляются с обычным disclaimer:, в то время как быстрее не все возможные испытания были выполнены, и пользователь должен проверить правильность ввода данных, прежде чем звонить и возвращаться ... blah, blah, blah .. Но они довольно полезны:

Я считаю, что правильная атрибуция идет до Geeks for Geeks Pow(x,n), как указано голубой луной. Я давно потерял ссылки ... Это похоже на них. (минус два или два).

/* Function to calculate x raised to the power y 

    Time Complexity: O(n) 
    Space Complexity: O(1) 
    Algorithmic Paradigm: Divide and conquer. 
*/ 
int power1 (int x, unsigned int y) 
{ 
    if (y == 0) 
     return 1; 
    else if ((y % 2) == 0) 
     return power1 (x, y/2) * power1 (x, y/2); 
    else 
     return x * power1 (x, y/2) * power1 (x, y/2); 

} 

/* Function to calculate x raised to the power y in O(logn) 
    Time Complexity of optimized solution: O(logn) 
*/ 
int power2 (int x, unsigned int y) 
{ 
    int temp; 
    if (y == 0) 
     return 1; 

    temp = power2 (x, y/2); 
    if ((y % 2) == 0) 
     return temp * temp; 
    else 
     return x * temp * temp; 
} 

/* Extended version of power function that can work 
for float x and negative y 
*/ 
float powerf (float x, int y) 
{ 
    float temp; 
    if (y == 0) 
    return 1; 
    temp = powerf (x, y/2); 
    if ((y % 2) == 0) { 
     return temp * temp; 
    } else { 
     if (y > 0) 
      return x * temp * temp; 
     else 
      return (temp * temp)/x; 
    } 
} 

/* Extended version of power function that can work 
for double x and negative y 
*/ 
double powerd (double x, int y) 
{ 
    double temp; 
    if (y == 0) 
    return 1; 
    temp = powerd (x, y/2); 
    if ((y % 2) == 0) { 
     return temp * temp; 
    } else { 
     if (y > 0) 
      return x * temp * temp; 
     else 
      return (temp * temp)/x; 
    } 
} 

Answer 2

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

Answer 3

нерекурсивна без ответа с плавающей точкой

Заменить uintmax_t/intmax_t с типом вашего желания. Переполнение не обнаружено.

uintmax_t powjuu(unsigned x, unsigned y) { 
    uintmax_t z = 1; 
    uintmax_t base = x; 
    while (y) { 
    if (y & 1) { // or y%2 
     z *= base; 
    } 
    y >>= 1; // or y /= 2 
    base *= base; 
    } 
    return z; 
} 

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; 
    while (y) { 
    if (y & 1) { 
     z *= base; 
    } 
    y >>= 1; 
    base *= base; 
    } 
    return z; 
}