c++ - ultima - Una forma eficiente de calcular p ^ q(exponenciación), donde q es un número entero

teoria de logaritmos

Question

¿Cuál es una forma eficiente de calcular p ^q , donde q es un número entero?

Answer 1

Supongo que por ^ te refieres a la función de potencia, y no a modo de bit xor.

El desarrollo de una función de potencia eficiente para cualquier tipo de p y cualquier integral positiva q es el tema de una sección completa, 3.2, en el libro Elementos de programación de Stepanov y McJones . El idioma en el libro no es C ++, pero se traduce muy fácilmente a C ++.

Cubre varias optimizaciones, incluida la exponenciación por escuadrado, la conversión a recursión de la cola y luego la iteración, y la eliminación de la variable de acumulación, y relaciona las optimizaciones con las nociones de regularidad de tipo y operaciones asociativas para demostrar que funciona para todos estos tipos.

Answer 2

Suponiendo que ^ significa exponenciación y que q es una variable de tiempo de ejecución, use std::pow(double, int) .

EDITAR: Para estar completo debido a los comentarios sobre esta respuesta: hice la pregunta ¿Por qué se eliminó std :: pow (double, int) de C ++ 11? sobre la función faltante y, de hecho, pow(double, int) no se eliminó en C ++ 0x, solo se cambió el idioma. Sin embargo, parece que las bibliotecas en realidad no pueden optimizarlo debido a problemas de precisión del resultado.

Incluso dado que seguiría usando pow hasta que la medición me mostrara que necesitaba ser optimizado.

Answer 3

La exponencia por escuadrado utiliza solo multiplicaciones de O (lg q ).

template <typename T>
T expt(T p, unsigned q)
{
    T r(1);

    while (q != 0) {
        if (q % 2 == 1) {    // q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }

    return r;
}

Esto debería funcionar en cualquier monoid ( T , operator* ) donde una T construida a partir de 1 es el elemento de identidad. Eso incluye todos los tipos numéricos.

Extender esto a signed q es fácil: simplemente divida uno por el resultado de lo anterior para el valor absoluto de q (pero como de costumbre, tenga cuidado al calcular el valor absoluto).