c++ - raiz - ¿Qué es más eficiente? ¿Usar pow to square o simplemente multiplicarlo consigo mismo?

raiz cuadrada en c++ sqrt

Question

¿Cuál de estos dos métodos es más eficiente en C? Y qué tal:

pow(x,3)

vs.

x*x*x // etc?

Answer 1

Esa es la clase incorrecta de pregunta. La pregunta correcta sería: "¿Cuál es más fácil de entender para los lectores humanos de mi código?"

Si la velocidad es importante (más adelante), no pregunte, sino mida. (Y antes de eso, mida si la optimización de esto realmente hará una diferencia notable). Hasta entonces, escriba el código para que sea más fácil de leer.

Editar
Para dejar esto en claro (aunque ya debería haberlo sido): las aceleraciones de avance generalmente provienen de cosas como usar mejores algoritmos , mejorar la localización de datos , reducir el uso de memoria dinámica , precomputar resultados , etc. Rara vez provienen de micro -optimizar llamadas de función única , y donde lo hacen, lo hacen en muy pocos lugares , lo que solo se puede encontrar mediante perfiles cuidadosos (y lentos), con más frecuencia que nunca se pueden acelerar haciendo cosas muy poco intuitivas (como insertar instrucciones noop ), y lo que es una optimización para una plataforma a veces es una pesimización para otra (por eso es necesario medir, en lugar de preguntar, porque no conocemos ni tenemos completamente su entorno).

Permítanme subrayar esto de nuevo: incluso en las pocas aplicaciones en las que estas cosas importan, no importan en la mayoría de los lugares donde se usan, y es muy poco probable que encuentren los lugares donde importan mirando el código. Realmente necesita identificar los puntos calientes primero , porque de lo contrario, la optimización del código es solo una pérdida de tiempo .

Incluso si una sola operación (como calcular el cuadrado de algún valor) ocupa el 10% del tiempo de ejecución de la aplicación (que es bastante raro), e incluso si optimiza, ahorra el 50% del tiempo necesario para esa operación (que IME es incluso mucho, mucho más raro), todavía hiciste que la aplicación tomara solo un 5% menos de tiempo .
Sus usuarios necesitarán un cronómetro para notarlo. (Supongo que en la mayoría de los casos, cualquier cosa con un 20% de aceleración pasa desapercibida para la mayoría de los usuarios. Y son cuatro los puntos que debes buscar).

Answer 2

La forma más eficiente es considerar el crecimiento exponencial de las multiplicaciones. Verifique este código para p ^ q:

template <typename T>
T expt(T p, unsigned q){
    T r =1;
    while (q != 0) {
        if (q % 2 == 1) {    // if q is odd
            r *= p;
            q--;
        }
        p *= p;
        q /= 2;
    }
    return r;
}

Answer 3

Probé la diferencia de rendimiento entre x*x*... vs pow(x,i) para i pequeño usando este código:

#include <cstdlib>
#include <cmath>
#include <boost/date_time/posix_time/posix_time.hpp>

inline boost::posix_time::ptime now()
{
    return boost::posix_time::microsec_clock::local_time();
}

#define TEST(num, expression) /
double test##num(double b, long loops) /
{ /
    double x = 0.0; /
/
    boost::posix_time::ptime startTime = now(); /
    for (long i=0; i<loops; ++i) /
    { /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
        x += expression; /
    } /
    boost::posix_time::time_duration elapsed = now() - startTime; /
/
    std::cout << elapsed << " "; /
/
    return x; /
}

TEST(1, b)
TEST(2, b*b)
TEST(3, b*b*b)
TEST(4, b*b*b*b)
TEST(5, b*b*b*b*b)

template <int exponent>
double testpow(double base, long loops)
{
    double x = 0.0;

    boost::posix_time::ptime startTime = now();
    for (long i=0; i<loops; ++i)
    {
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
        x += std::pow(base, exponent);
    }
    boost::posix_time::time_duration elapsed = now() - startTime;

    std::cout << elapsed << " ";

    return x;
}

int main()
{
    using std::cout;
    long loops = 100000000l;
    double x = 0.0;
    cout << "1 ";
    x += testpow<1>(rand(), loops);
    x += test1(rand(), loops);

    cout << "/n2 ";
    x += testpow<2>(rand(), loops);
    x += test2(rand(), loops);

    cout << "/n3 ";
    x += testpow<3>(rand(), loops);
    x += test3(rand(), loops);

    cout << "/n4 ";
    x += testpow<4>(rand(), loops);
    x += test4(rand(), loops);

    cout << "/n5 ";
    x += testpow<5>(rand(), loops);
    x += test5(rand(), loops);
    cout << "/n" << x << "/n";
}

Los resultados son:

1 00:00:01.126008 00:00:01.128338 
2 00:00:01.125832 00:00:01.127227 
3 00:00:01.125563 00:00:01.126590 
4 00:00:01.126289 00:00:01.126086 
5 00:00:01.126570 00:00:01.125930 
2.45829e+54

Tenga en cuenta que acumulo el resultado de cada cálculo de pow para asegurarme de que el compilador no lo optimice.

Si utilizo la versión std::pow(double, double) y los loops = 1000000l , obtengo:

1 00:00:00.011339 00:00:00.011262 
2 00:00:00.011259 00:00:00.011254 
3 00:00:00.975658 00:00:00.011254 
4 00:00:00.976427 00:00:00.011254 
5 00:00:00.973029 00:00:00.011254 
2.45829e+52

Esto está en un Intel Core Duo con Ubuntu 9.10 de 64 bits. Compilado usando gcc 4.4.1 con optimización -o2.

Entonces en C, sí x*x*x será más rápido que pow(x, 3) , porque no hay sobrecarga de pow(double, int) . En C ++, será más o menos lo mismo. (Suponiendo que la metodología en mi prueba es correcta)

Esto es en respuesta al comentario hecho por An Markm:

Incluso si se emitió una directiva using namespace std , si el segundo parámetro para pow es un int , entonces se <cmath> sobrecarga std::pow(double, int) desde <cmath> lugar de ::pow(double, double) desde <math.h> .

Este código de prueba confirma ese comportamiento:

#include <iostream>

namespace foo
{

    double bar(double x, int i)
    {
        std::cout << "foo::bar/n";
        return x*i;
    }


}

double bar(double x, double y)
{
    std::cout << "::bar/n";
    return x*y;
}

using namespace foo;

int main()
{
    double a = bar(1.2, 3); // Prints "foo::bar"
    std::cout << a << "/n";
    return 0;
}

Answer 4

Si el exponente es constante y pequeño, amplíelo, minimizando el número de multiplicaciones. (Por ejemplo, x^4 no es óptimamente x*x*x*x , pero y*y donde y=x*x . Y x^5 es y*y*x donde y=x*x . Y así sucesivamente. ) Para exponentes enteros constantes, simplemente escriba la forma optimizada ya; con exponentes pequeños, esta es una optimización estándar que debe realizarse ya sea que el código haya sido perfilado o no. La forma optimizada será más rápida en un porcentaje tan grande de casos que básicamente siempre vale la pena hacerlo.

(Si usa Visual C ++, std::pow(float,int) realiza la optimización a la que aludo, por lo que la secuencia de operaciones está relacionada con el patrón de bits del exponente. No garantizo que el compilador desenrollará el ciclo para usted, sin embargo, así que todavía vale la pena hacerlo a mano).

[edit] BTW pow tiene una tendencia (no) sorprendente a aparecer en los resultados del perfilador. Si no lo necesita en absoluto (es decir, el exponente es grande o no es una constante), y le preocupa el rendimiento, entonces es mejor escribir el código óptimo y esperar a que el generador de perfiles le diga que es (sorprendentemente) ) perdiendo el tiempo antes de pensar más. (La alternativa es llamar a pow y hacer que el generador de perfiles le diga que (como era de esperar) está perdiendo el tiempo; está recortando este paso al hacerlo inteligentemente).

Answer 5

También me preguntaba sobre el problema de rendimiento, y esperaba que el compilador optimizara esto, según la respuesta de @EmileCormier. Sin embargo, me preocupaba que el código de prueba que mostraba aún le permitiera al compilador optimizar la llamada std :: pow (), ya que siempre se usaban los mismos valores en la llamada, lo que permitiría al compilador almacenar los resultados y reutilizarlo en el ciclo, esto explicaría los tiempos de ejecución casi idénticos para todos los casos. Así que también lo eché un vistazo.

Aquí está el código que usé (test_pow.cpp):

#include <iostream>                                                                                                                                                                                                                       
#include <cmath>
#include <chrono>

class Timer {
  public:
    explicit Timer () : from (std::chrono::high_resolution_clock::now()) { }

    void start () {
      from = std::chrono::high_resolution_clock::now();
    }

    double elapsed() const {
      return std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - from).count() * 1.0e-6;
    }

  private:
    std::chrono::high_resolution_clock::time_point from;
};

int main (int argc, char* argv[])
{
  double total;
  Timer timer;



  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += std::pow (i,2);
  std::cout << "std::pow(i,2): " << timer.elapsed() << "s (result = " << total << ")/n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += i*i;
  std::cout << "i*i: " << timer.elapsed() << "s (result = " << total << ")/n";

  std::cout << "/n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += std::pow (i,3);
  std::cout << "std::pow(i,3): " << timer.elapsed() << "s (result = " << total << ")/n";

  total = 0.0;
  timer.start();
  for (double i = 0.0; i < 1.0; i += 1e-8)
    total += i*i*i;
  std::cout << "i*i*i: " << timer.elapsed() << "s (result = " << total << ")/n";


  return 0;
}

Esto fue compilado usando:

g++ -std=c++11 [-O2] test_pow.cpp -o test_pow

Básicamente, la diferencia es el argumento para std :: pow () es el contador de bucles. Como temía, la diferencia en el rendimiento es pronunciada. Sin el distintivo -O2, los resultados en mi sistema (Arch Linux 64-bit, g ++ 4.9.1, Intel i7-4930) fueron:

std::pow(i,2): 0.001105s (result = 3.33333e+07)
i*i: 0.000352s (result = 3.33333e+07)

std::pow(i,3): 0.006034s (result = 2.5e+07)
i*i*i: 0.000328s (result = 2.5e+07)

Con la optimización, los resultados fueron igualmente llamativos:

std::pow(i,2): 0.000155s (result = 3.33333e+07)
i*i: 0.000106s (result = 3.33333e+07)

std::pow(i,3): 0.006066s (result = 2.5e+07)
i*i*i: 9.7e-05s (result = 2.5e+07)

Así que parece que el compilador al menos intenta optimizar el caso std :: pow (x, 2), pero no el caso std :: pow (x, 3) (tarda ~ 40 veces más que el std :: pow (x, 2) caso). En todos los casos, la expansión manual tuvo un mejor rendimiento, pero particularmente para el caso de potencia 3 (60 veces más rápido). Esto definitivamente vale la pena tener en cuenta si se ejecuta std :: pow () con potencias enteras mayores que 2 en un ciclo cerrado ...

Answer 6

x*x o x*x*x será más rápido que pow , ya que pow debe tratar con el caso general, mientras que x*x es específico. Además, puede elide la llamada de función y tal.

Sin embargo, si se encuentra micro-optimizando de esta manera, necesita obtener un perfilador y hacer un perfil serio. La abrumadora probabilidad es que nunca notarías ninguna diferencia entre los dos.