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
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.
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).
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.
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.
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?.
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 ?
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
joder...definitivamente este ha sido un mal año para mi :?
Cada vez que edito un mensaje me lo pone como new reply :shock:
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.
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 ..... };
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!
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;
}
}
shephiroth: pues escribiste lo mismo que yo!
Saludos!
Pues ahora q lo dices...si, la idea es la misma. Y ahora que lo veo me quedo con un par de dudas:
1- Que es mas rapido, (1<<i) o precalcularlos?
2- Pq usas double?? Se quedará pequeña enseguida.
3- Calcular el log2n(n); te va a llevar demasiadas multiplicaciones ^^;
1) En un 486 seria mas rapido precalculado pero en un pentium III ya no lo creo.
Pero igual el compilador se dará cuenta de hacer una variable intermedia e ir Vi<<=1, con lo cual en cualquier arquitectura irías mas rapido. Por ahí uno se mal acostumbra a los compiladores modernos.
2) Double es casí la mas grande que se puede usar y el standart en calculos matematicos para la libreria standart de C.
3) Calcular log2(n) es:
int log2(int n) {
for(int i=1; i<32; i++) if(!(n>>i)) break;
return i-1;
}
Incluso si sos muy loco podes hacer una busqueda binaria!
frikada:
template<int x,int n> class pow
{
enum{ res = x*pow<x,n-1>::res };
};
template<int x> class pow<x,0>
{
enum { res = 1 };
};
:P
borrado
Me parece que alguien esta leyendo sobre templates y se esta enamorando de ellos ...
Si, la verdad es que son una adicción pero tengo muchos problemas con el compilador culpa de eso y con el tiempo te frustran.
No se si anda pero no me pude resistir:
Log2n en tiempo de compilación con busqueda binaria:
template<int a, int b, bool cond> struct switch { };
template<int a, int b> struct switch<true> { enum { res=a }; };
template<int a, int b> struct switch<false> { enum { res=b }; };
template<int n> struct log2 {
template<int p> struct eval { enum { res = n>>p }; };
template<int l, int d> struct search {
enum {
p = d/2,
ev = eval<l+p>::res,
res = search<switch<l, l+p, !ev>::res, p>::res;
};
};
template<int l> struct search<0> { enum { res=l; }; };
enum { res = search<0,31>::res; };
};
Cita de: "Pogacha"Me parece que alguien esta leyendo sobre templates y se esta enamorando de ellos ...
Realmente la metaprogramación esta es prácticamente inservible, por dos razones:
1) en tiempo de compilación no tiene nada de utilidad
2) para hacer algo simple se complica tanto la cosa que es preferible no usarlo.
Citar
Realmente la metaprogramación esta es prácticamente inservible, por dos razones:
1) en tiempo de compilación no tiene nada de utilidad
2) para hacer algo simple se complica tanto la cosa que es preferible no usarlo.
No entinedo lo que dices, si bien estos casos son unicamente para fines de "estudio", en muchas aplicaciones no tienen remplazo.
PD:
int log2(int n) {
for(int i=1; i<32; i++) if(!(n>>i)) break;
return i-1;
}
solo funcionaria en VC6.0
Lo correcto seria:
int log2(int n) {
int i;
for(i=1; i<32; i++) if(!(n>>i)) break;
return i-1;
}
o mejor aun:
int log2(int n) {
int i=0;
while( n>>=1 ) ++i;
return i;
}Con una busqueda binaria reduces el max de 32 a la constante de 5 comparaciones con una ligera elebacion de la constante ...