Calculando x^n para n entero de la forma más rápida

[McBain]

Creo que el título es autoexplicativo, estoy haciendo una función que calcule x^n para n entero (la utilizaré muchas veces, por lo que necesito que sea rápida). La primera solución que me vino a la cabeza fue supongo que la típica de

Código: [Seleccionar]


total=1;
while(n--!=0)
  total*=x;


Pero, me he dado cuenta de que si quisiera calcular x^4 en vez de realizar 3 productos, podría reducirlo a 2, podría calcular x^2 y luego multiplicar ese valor por el mismo. Así, para cualquier n que sea potencia de 2. También, por ejemplo para calcular x^7,  no necesito hacer 6 productos, podemos hacer y=x*x, z=y*y, total=z/x.
¿Alguien conoce algun algoritmo para evaluar x^n con el menor número de productos posibles?
Saludos

[ZüNdFoLGe]

un típico problema de programación dinámica...debes almacenar en una tabla los valores previamente calculados y al restar el exponente-- por cada vez que multipliques ver si tienes en la tabla el valor previamente calculado...si es así lo usas, sino lo metes en la tabla. Si mal no recuerdo esto se ha tratado en estos foros...y si aún mal no recuerdo puse el algoritmo en c++ para ello.

[LC0]

Con programación dinámica el algoritmo seguiría siendo O(n).
Está el algoritmo de potencia rápida que te reduce el tiempo a  ser O(log(n)).
El truco está en que, si el exponente es par, base^exp == (base*base)^(exp/2).

[swapd0]

Por mucho que cambies el algoritmo, no creo que ganes mucho, ya que las multiplicaciones son rapidas (desde hace tiempo), esto no es como programar un 8086, o un 68000.

[Pogacha]

Fijate si esto anda ...

Código: [Seleccionar]

double Potencia_Pogachense( double x, int n)
{
   double acum = 1.0;
   double iter = x;
   int log2n = log2(n); // esta es facil

   for(int i=0; i<=log2n; ++i)
   {
       if( (n & (1<<i)) != 0) acum*=iter;
       iter*=iter;
   }
   return acum;
}

Lo escribi al vuelo asi que prueba y dime.
Saludos.

[marcode]

Por mucho que cambies el algoritmo, no creo que ganes mucho, ya que las multiplicaciones son rapidas (desde hace tiempo), esto no es como programar un 8086, o un 68000.

Yo incluso creo que cambiarlo hará que vaya más lento, las asignaciones, comprobaciones, sumas, etc. también consumen, y las divisiones más.

Sería importante saber cuánto va a ser el valor de n normalmente.

Casi mejor que te lo codifique algún gurú en ensamblador y hacer una función inline ¿no?.

[ZüNdFoLGe]

El truco está en que, si el exponente es par, base^exp == (base*base)^(exp/2)

Y si el exponente es impar ?

[fiero]

Y si el exponente es impar ?

Supongo que se le resta 1 al exponente y el resultado final se multiplica por el número

un saludo

[ZüNdFoLGe]

joder...definitivamente este ha sido un mal año para mi  :?

[ZüNdFoLGe]

Cada vez que edito un mensaje me lo pone como new reply  :shock:

[burb]

A ver esta alternativa, quizás no te sirva :? pero rapida si es.

Código: [Seleccionar]


inline double pow2(double x) { return x*x; }
inline double pow3(double x) { return x*x*x; }
inline double pow4(double x) { return x*x*x*x; }
inline double pow5(double x) { return x*x*x*x*x; }
....

double (*pow[])(double& x) = { pow2, pow2, pow2, pow3, pow4, pow5, ... };

se usaría de dos maneras:

resultado = pow4(x);
resultado = pow[n](x);



Creo que no necesita mucha más explicación.

[burb]

corrección   :

Código: [Seleccionar]


inline double pow0(double x) { return 1; }
inline double pow1(double x) { return x; }
inline double pow2(double x) { return x*x; }
inline double pow3(double x) { return x*x*x; }
....

double (*pow[])(double x) = { pow0, pow1, pow2, pow3 ..... };



[Pogacha]

Don burb, pasa que se desaprovecha la dinamica:

x*x*x*x*x
es mejor como

a = x * x;
return a * a * x;

Mi algoritmo pretendia eso ... pero no me han dicho si funciona aún  :?

Saludos!

[shephiroth]

Buenas.

No se en terminos de tiempo de computacion si esto te servirá, pero si lo unico que te interesa es minimizar multiplicaciones:

Código: [Seleccionar]


class exponente
{
byte bases[10];
exponente()
{
byte a = 1;
byte pos;
bases[0]=1;
for (pos=1;pos<10;pos++)
bases[pos]=bases[pos-1]*2;
}
int potencia(int num, int exp)
{
int res = 1;
int pos=0;
while (exp>bases[pos])
{
if (exp & base[pos]) res *=num;
num*=num;
pos++;
}
return res;
}
}


[Pogacha]

shephiroth: pues escribiste lo mismo que yo!
Saludos!