una - potencia en c++ con while

¿Cuál es la forma correcta de elevar un número entero a un poder entero positivo en C++?

Question

Sabemos que, por diversas razones , no hay una función de potencia de enteros estándar en C ++. Estoy realizando una aritmética exacta con enteros bastante pequeños, ¿cuál es la forma correcta de calcular potencias?

Answer 1

Además de las otras respuestas aquí, también hay un buen artículo en Wikipedia que explica varias implementaciones diferentes aquí -> LINK

Answer 2

La exponenciación rápida estándar utiliza el escuadrado repetido:

uint_t power(uint_t base, uint_t exponent)
{
    uint_t result = 1;

    for (uint_t term = base; exponent != 0; term = term * term)
    {
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
    }

    return result;
}

El número de pasos es logarítmico en el valor del exponent . Este algoritmo se puede extender trivialmente a la exponenciación modular.

Actualización: Aquí hay una versión modificada del algoritmo que realiza una multiplicación menos y maneja algunos casos triviales de manera más eficiente. Además, si sabes que el exponente nunca es cero y la base nunca es cero o uno, incluso podrías eliminar los controles iniciales:

uint_t power_modified(uint_t base, uint_t exponent)
{
    if (exponent == 0) { return 1;    }
    if (base < 2)      { return base; }

    uint_t result = 1;

    for (uint_t term = base; ; term = term * term)
    { 
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
        if (exponent == 0)     { break; }
    }

    return result;
}

Answer 3

Puedes usar std::pow(double a, double b) . ¡No habrá inexactitudes si tanto a , b como el resultado encajan en un entero de 32 bits!

La razón es que la precisión doble de 64 bits cubre completamente el rango de enteros de 32 bits.

Answer 4

Si bien la respuesta de Kerrek es correcta, también hay una función "secreta" en g ++ para hacerlo de manera eficiente. Si observa la función de potencia SGI, se puede adaptar fácilmente para hacer lo que quiera:

http://www.sgi.com/tech/stl/power.html

En g ++, esto se implementa como __gnu_cxx::power . Aunque probablemente no deberías usar estas cosas en el código de producción ...