c++ - sacar - programa para calcular una potencia

¿Alguna forma más rápida que pow() para calcular una potencia entera de 10 en C++? (9)

Sé que el poder de 2 se puede implementar utilizando el operador << ¿Qué pasa con el poder de 10? ¿Te gusta 10 ^ 5? ¿Hay alguna manera más rápida que pow (10,5) en C ++? Es un cálculo bastante sencillo a mano. Pero no parece fácil para las computadoras debido a la representación binaria de los números ... Supongamos que solo estoy interesado en potencias de enteros, 10 ^ n, donde n es un entero.

¡Ciertamente hay formas de calcular potencias integrales de 10 más rápido que usando std::pow() ! La primera realización es que pow(x, n) se puede implementar en tiempo O (log n). La siguiente realización es que pow(x, 10) es lo mismo que (x << 3) * (x << 1) . Por supuesto, el compilador sabe lo último, es decir, cuando está multiplicando un entero por la constante entera 10, el compilador hará lo que sea más rápido para multiplicar por 10. En base a estas dos reglas, es fácil crear cálculos rápidos, incluso si x es un tipo entero grande

En caso de que estés interesado en juegos como este:

Una versión genérica de O (log n) de poder se discute en Elementos de programación .
Muchos de los "trucos" interesantes con enteros se discuten en Hacker''s Delight .

Algo como esto:

int quick_pow10(int n) { static int pow10[10] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; return pow10[n]; }

Obviamente, puede hacer lo mismo por long long .

Esto debería ser varias veces más rápido que cualquier método de competencia. Sin embargo, es bastante limitado si tiene muchas bases (aunque la cantidad de valores disminuye considerablemente con bases más grandes), por lo que si no hay una gran cantidad de combinaciones, todavía es factible.

A modo de comparación:

#include <iostream> #include <cstdlib> #include <cmath> static int quick_pow10(int n) { static int pow10[10] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 }; return pow10[n]; } static int integer_pow(int x, int n) { int r = 1; while (n--) r *= x; return r; } static int opt_int_pow(int n) { int r = 1; const int x = 10; while (n) { if (n & 1) { r *= x; n--; } else { r *= x * x; n -= 2; } } return r; } int main(int argc, char **argv) { long long sum = 0; int n = strtol(argv[1], 0, 0); const long outer_loops = 1000000000; if (argv[2][0] == ''a'') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += quick_pow10(n); } } } if (argv[2][0] == ''b'') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += integer_pow(10,n); } } } if (argv[2][0] == ''c'') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += opt_int_pow(n); } } } std::cout << "sum=" << sum << std::endl; return 0; }

Compilado con g ++ 4.6.3, usando -Wall -O2 -std=c++0x , da los siguientes resultados:

$ g++ -Wall -O2 -std=c++0x pow.cpp $ time ./a.out 8 a sum=100000000000000000 real 0m0.124s user 0m0.119s sys 0m0.004s $ time ./a.out 8 b sum=100000000000000000 real 0m7.502s user 0m7.482s sys 0m0.003s $ time ./a.out 8 c sum=100000000000000000 real 0m6.098s user 0m6.077s sys 0m0.002s

(También tenía una opción para usar pow , pero tomó 1m22.56s cuando lo probé por primera vez, así que lo eliminé cuando decidí tener la variante de bucle optimizada)

Aquí hay una puñalada:

// specialize if you have a bignum integer like type you want to work with: template<typename T> struct is_integer_like:std::is_integral<T> {}; template<typename T> struct make_unsigned_like:std::make_unsigned<T> {}; template<typename T, typename U> T powT( T base, U exponent ) { static_assert( is_integer_like<U>::value, "exponent must be integer-like" ); static_assert( std::is_same< U, typename make_unsigned_like<U>::type >::value, "exponent must be unsigned" ); T retval = 1; T& multiplicand = base; if (exponent) { while (true) { // branch prediction will be awful here, you may have to micro-optimize: retval *= (exponent&1)?multiplicand:1; // or /2, whatever -- `>>1` is probably faster, esp for bignums: exponent = exponent>>1; if (!exponent) break; multiplicand *= multiplicand; } } return retval; }

Lo que está pasando arriba es algunas cosas.

Primero, por lo que el soporte de BigNum es barato, está modelado. Fuera de la caja, admite cualquier tipo de base que admita *= own_type y se puede convertir implícitamente a int , o int se puede convertir implícitamente a él (si ambos son verdaderos, se producirán problemas), y es necesario que especialice alguna template s para indicar que el tipo de exponente involucrado es a la vez sin signo y de tipo entero.

En este caso, enteros y sin signo significa que soporta &1 devolviendo bool y >>1 devolviendo algo con lo que se puede construir y eventualmente (después de repetirse >>1 s) alcanza un punto en el que evaluarlo en un contexto bool devuelve false . Utilicé clases de rasgos para expresar la restricción, porque el uso ingenuo por un valor como -1 compilaría y (en algunas plataformas) se repetirá para siempre, mientras que (en otras) no.

El tiempo de ejecución para este algoritmo, suponiendo que la multiplicación es O (1), es O (lg (exponente)), donde lg (exponente) es la cantidad de veces que se tarda en <<1 el exponent antes de que se evalúe como false en un bool ean contexto. Para los tipos enteros tradicionales, este sería el registro binario del valor del exponent : por lo tanto, no más de 32.

También eliminé todas las ramas dentro del bucle (o, lo hice obvio para los compiladores existentes de que no se necesita ninguna rama, más precisamente), con solo la rama de control (que es cierta de manera uniforme hasta que es falsa una vez). Posiblemente eliminar incluso esa rama podría valer la pena para bases altas y exponentes bajos ...

Basado en el enfoque de Mats Petersson , pero compilar la generación de tiempo de caché.

#include <iostream> #include <limits> #include <array> // digits template <typename T> constexpr T digits(T number) { return number == 0 ? 0 : 1 + digits<T>(number / 10); } // pow // https://.com/questions/24656212/why-does-gcc-complain-error-type-intt-of-template-argument-0-depends-on-a // unfortunatly we can''t write `template <typename T, T N>` because of partial specialization `PowerOfTen<T, 1>` template <typename T, uintmax_t N> struct PowerOfTen { enum { value = 10 * PowerOfTen<T, N - 1>::value }; }; template <typename T> struct PowerOfTen<T, 1> { enum { value = 1 }; }; // sequence template<typename T, T...> struct pow10_sequence { }; template<typename T, T From, T N, T... Is> struct make_pow10_sequence_from : make_pow10_sequence_from<T, From, N - 1, N - 1, Is...> { // }; template<typename T, T From, T... Is> struct make_pow10_sequence_from<T, From, From, Is...> : pow10_sequence<T, Is...> { // }; // base10list template <typename T, T N, T... Is> constexpr std::array<T, N> base10list(pow10_sequence<T, Is...>) { return {{ PowerOfTen<T, Is>::value... }}; } template <typename T, T N> constexpr std::array<T, N> base10list() { return base10list<T, N>(make_pow10_sequence_from<T, 1, N+1>()); } template <typename T> constexpr std::array<T, digits(std::numeric_limits<T>::max())> base10list() { return base10list<T, digits(std::numeric_limits<T>::max())>(); }; // main pow function template <typename T> static T template_quick_pow10(T n) { static auto values = base10list<T>(); return values[n]; } // client code int main(int argc, char **argv) { long long sum = 0; int n = strtol(argv[1], 0, 0); const long outer_loops = 1000000000; if (argv[2][0] == ''t'') { for(long i = 0; i < outer_loops / n; i++) { for(int j = 1; j < n+1; j++) { sum += template_quick_pow10(n); } } } std::cout << "sum=" << sum << std::endl; return 0; }

El código no contiene quick_pow10, integer_pow, opt_int_pow para una mejor legibilidad, pero las pruebas se realizan con ellos en el código.

Compilado con gcc versión 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5), usando -Wall -O2 -std = c ++ 0x, da los siguientes resultados:

$ g++ -Wall -O2 -std=c++0x main.cpp $ time ./a.out 8 a sum=100000000000000000 real 0m0.438s user 0m0.432s sys 0m0.008s $ time ./a.out 8 b sum=100000000000000000 real 0m8.783s user 0m8.777s sys 0m0.004s $ time ./a.out 8 c sum=100000000000000000 real 0m6.708s user 0m6.700s sys 0m0.004s $ time ./a.out 8 t sum=100000000000000000 real 0m0.439s user 0m0.436s sys 0m0.000s

Esta función calculará x ^ y mucho más rápido que pow. En caso de valores enteros.

int pot(int x, int y){ int solution = 1; while(y){ if(y&1) solution*= x; x *= x; y >>= 1; } return solution;

}

Puedes usar la tabla de búsqueda que será, con mucho, la más rápida.

También puedes considerar usar this :

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

Sin multiplicación y sin versión de mesa:

//Nx10^n int Npow10(int N, int n){ N <<= n; while(n--) N += N << 2; return N; }

Una función de potencia entera (que no implica conversiones y cálculos de punto flotante) puede ser mucho más rápida que pow() :

int integer_pow(int x, int n) { int r = 1; while (n--) r *= x; return r; }

Edit: benchmarked - el método de exponenciación de enteros ingenuos parece superar al punto flotante uno alrededor de un factor de dos:

h2co3-macbook:~ h2co3$ cat quirk.c #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <errno.h> #include <string.h> #include <math.h> int integer_pow(int x, int n) { int r = 1; while (n--) r *= x; return r; } int main(int argc, char *argv[]) { int x = 0; for (int i = 0; i < 100000000; i++) { x += powerfunc(i, 5); } printf("x = %d/n", x); return 0; } h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=integer_pow h2co3-macbook:~ h2co3$ time ./quirk x = -1945812992 real 0m1.169s user 0m1.164s sys 0m0.003s h2co3-macbook:~ h2co3$ clang -Wall -o quirk quirk.c -Dpowerfunc=pow h2co3-macbook:~ h2co3$ time ./quirk x = -2147483648 real 0m2.898s user 0m2.891s sys 0m0.004s h2co3-macbook:~ h2co3$

Una solución para cualquier base utilizando la meta-programación de plantillas:

template<int E, int N> struct pow { enum { value = E * pow<E, N - 1>::value }; }; template <int E> struct pow<E, 0> { enum { value = 1 }; };

Luego se puede usar para generar una tabla de búsqueda que se puede usar en tiempo de ejecución:

template<int E> long long quick_pow(unsigned int n) { static long long lookupTable[] = { pow<E, 0>::value, pow<E, 1>::value, pow<E, 2>::value, pow<E, 3>::value, pow<E, 4>::value, pow<E, 5>::value, pow<E, 6>::value, pow<E, 7>::value, pow<E, 8>::value, pow<E, 9>::value }; return lookupTable[n]; }

Esto debe usarse con las marcas correctas del compilador para detectar los posibles desbordamientos.

Ejemplo de uso:

for(unsigned int n = 0; n < 10; ++n) { std::cout << quick_pow<10>(n) << std::endl; }