Stratos: Punto de Encuentro de Desarrolladores

¡Bienvenido a Stratos!

Acceder

Foros





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

Iniciado por McBain, 06 de Diciembre de 2006, 04:12:25 PM

« anterior - próximo »

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


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 ...

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

Cita de: "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.

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?.
size=9]afortunadamente siempre ha habido alguien dispuesto a reinventar la rueda, de lo contrario seguiríamos usando un disco de piedra con un agujero.[/size]

ZüNdFoLGe

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

Y si el exponente es impar ?

fiero

Cita de: "ZüNdFoLGe"
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
www.videopanoramas.com Videopanoramas 3D player

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.


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  8) :


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:


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!






Stratos es un servicio gratuito, cuyos costes se cubren en parte con la publicidad.
Por favor, desactiva el bloqueador de anuncios en esta web para ayudar a que siga adelante.
Muchísimas gracias.