La forma más eficiente de implementar una función de potencia basada en enteros pow(int, int)

4 minutos de lectura

avatar de usuario
doug t

¿Cuál es la forma más eficiente de elevar un número entero a la potencia de otro número entero en C?

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

// 5^5
pow(5,5) == 3125

  • Cuando dice “eficiencia”, debe especificar eficiente en relación con qué. ¿Velocidad? ¿Uso de memoria? Tamaño del código? Mantenibilidad?

    –Andy Lester

    2 de octubre de 2008 a las 17:26

  • ¿C no tiene una función pow()?

    – jalf

    30 de mayo de 2009 a las 13:07

  • si, pero eso funciona en flotantes o dobles, no en enteros

    –Nathan Fellman

    30 de mayo de 2009 a las 13:46

  • Si te apegas a lo real ints (y no alguna clase de gran int), muchas llamadas a ipow se desbordarán. Me hace preguntarme si hay una forma inteligente de precalcular una tabla y reducir todas las combinaciones que no se desbordan a una simple búsqueda de tabla. Esto requeriría más memoria que la mayoría de las respuestas generales, pero quizás sea más eficiente en términos de velocidad.

    – Adrián McCarthy

    07/01/2016 a las 17:15

  • pow() no es una función segura

    – EsmaeelE

    29/10/2017 a las 15:42

avatar de usuario
Pramod

Tenga en cuenta que exponenciación al cuadrado no es el método más óptimo. Probablemente sea lo mejor que puede hacer como método general que funciona para todos los valores de exponente, pero para un valor de exponente específico puede haber una secuencia mejor que necesite menos multiplicaciones.

Por ejemplo, si desea calcular x^15, el método de exponenciación al cuadrado le dará:

x^15 = (x^7)*(x^7)*x 
x^7 = (x^3)*(x^3)*x 
x^3 = x*x*x

Esto es un total de 6 multiplicaciones.

Resulta que esto se puede hacer usando “solo” 5 multiplicaciones a través de exponenciación de la cadena de suma.

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

No existen algoritmos eficientes para encontrar esta secuencia óptima de multiplicaciones. Desde Wikipedia:

El problema de encontrar la cadena de suma más corta no puede resolverse mediante programación dinámica, porque no satisface el supuesto de subestructura óptima. Es decir, no es suficiente descomponer la potencia en potencias más pequeñas, cada una de las cuales se calcula mínimamente, ya que las cadenas de suma para las potencias más pequeñas pueden estar relacionadas (para compartir cálculos). Por ejemplo, en la cadena de suma más corta para a¹⁵ anterior, el subproblema para a⁶ debe calcularse como (a³)² ya que a³ se reutiliza (a diferencia de, digamos, a⁶ = a²(a²)², que también requiere tres multiplicaciones ).

  • @JeremySalwen: como dice esta respuesta, la exponenciación binaria no es, en general, el método más óptimo. Actualmente no se conocen algoritmos eficientes para encontrar la secuencia mínima de multiplicaciones.

    –Eric Postpischil

    27 de diciembre de 2013 a las 21:32

  • @EricPostpischil, eso depende de su aplicación. Por lo general, no necesitamos un general algoritmo para trabajar todos números. Consulte El arte de la programación informática, vol. 2: Algoritmos Semiméricos

    – Pacerier

    16 de septiembre de 2014 a las 9:03


  • Hay una buena exposición de este problema exacto en De las matemáticas a la programación genérica por Alexander Stepanov y Daniel Rose. Este libro debería estar en el estante de todos los profesionales del software, en mi humilde opinión.

    –Toby Speight

    19 oct 2015 a las 10:03


  • Ver también es.wikipedia.org/wiki/….

    – izq.

    14 de abril de 2016 a las 11:27

  • Esto podría optimizarse para enteros porque hay potencias de enteros muy por debajo de 255 que no causarán desbordamiento para enteros de 32 bits. Puede almacenar en caché la estructura de multiplicación óptima para cada int. Me imagino que el código + datos aún sería más pequeño que simplemente almacenar en caché todos los poderes …

    – Josías Yoder

    17 de agosto de 2018 a las 19:25

  • Clang optimiza la recursión de la cola, pero gcc no lo hace a menos que reemplace el orden de multiplicación, es decir (e % 2 ? x : 1) * pow(x * x, e / 2) godbolt.org/z/EoWbfx5nc

    – Andy

    18 mayo 2021 a las 19:30

  • @Andy me di cuenta gcc estaba luchando, pero no me importa, ya que estoy usando esta función como un constexpr función.

    – usuario1095108

    19 de mayo de 2021 a las 5:54

Si necesitas elevar 2 a una potencia. La forma más rápida de hacerlo es cambiar de bit por el poder.

2 ** 3 == 1 << 3 == 8
2 ** 30 == 1 << 30 == 1073741824 (A Gigabyte)

  • ¿Hay una manera elegante de hacer esto para que 2 ** 0 == 1?

    – Rob Smallshire

    23 de noviembre de 2011 a las 21:39

  • @RobSmallshire Quizá 2 ** x = 1 << x (como 1<<0 es 1, tendrá que verificar si está en C std, o si depende de la plataforma, pero también podría hacerlo 2 ** x = x ? (1 << x) : 1 tenga en cuenta que 2 ** x tiene un significado en C, y eso no es poder 🙂

    – Deja Vu

    6 de mayo de 2021 a las 6:47


Un caso extremadamente especializado es, cuando necesitas decir 2^(-x a la y), donde x, por supuesto, es negativa e y es demasiado grande para hacer cambios en un int. Todavía puedes hacer 2^x en tiempo constante atornillando con un flotador.

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

Puede obtener más potencias de 2 utilizando un doble como tipo base. (Muchas gracias a los comentaristas por ayudar a cuadrar esta publicación).

También existe la posibilidad de que aprender más sobre flotadores IEEEpodrían presentarse otros casos especiales de exponenciación.

  • ¿Hay una manera elegante de hacer esto para que 2 ** 0 == 1?

    – Rob Smallshire

    23 de noviembre de 2011 a las 21:39

  • @RobSmallshire Quizá 2 ** x = 1 << x (como 1<<0 es 1, tendrá que verificar si está en C std, o si depende de la plataforma, pero también podría hacerlo 2 ** x = x ? (1 << x) : 1 tenga en cuenta que 2 ** x tiene un significado en C, y eso no es poder 🙂

    – Deja Vu

    6 de mayo de 2021 a las 6:47


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

  • No es mi voto, pero pow(1, -1) no sale del rango de int a pesar de un exponente negativo. Ahora que uno trabaja por accidente, como lo hace pow(-1, -1).

    – MSalters

    13 de agosto de 2015 a las 9:34

  • El único exponente negativo que puede no te haga salir el rango de int es -1. Y solo funciona si la base es 1 o -1. Entonces, solo hay dos pares (base, exp) con exp <0 que no conducirían a potencias no enteras. Aunque soy matemático y me gustan los cuantificadores, creo que en este caso, en la práctica, está bien decir que un exponente negativo te hace salir del reino de los enteros...

    – bartgol

    15 de agosto de 2017 a las 15:15


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad