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

[shephiroth]

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

[Pogacha]

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:

Código [Seleccionar] Expand

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!

[ethernet]

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

[ethernet]

borrado

[Pogacha]

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:

Código [Seleccionar] Expand


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


[ethernet]

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.

[Pogacha]

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:

Código [Seleccionar] Expand

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:

Código [Seleccionar] Expand

int log2(int n) {
int i;
for(i=1; i<32; i++) if(!(n>>i)) break;
return i-1;
}

o mejor aun:

Código [Seleccionar] Expand

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