¿Metafunción de raíz cuadrada?

Question

¿Es posible calcular la raíz cuadrada de un número entero con un metafunción con la siguiente firma:

template<unsigned int N> inline double sqrt(); 

(o tal vez usando la palabra clave constexpr, no sé lo que es el mejor). Con eso, sqrt<2>() sería reemplazado por 1.414... en tiempo de compilación.

¿Cuál sería la mejor implementación para una función de este tipo?

Answer 1

Esto puede no ser lo que está buscando, pero quería asegurarme de que se dio cuenta de que normalmente con la optimización el compilador calculará el resultado en tiempo de compilación de todos modos. Por ejemplo, si usted tiene este código:

void g() 
{ 
    f(sqrt(42)); 
} 

con g ++ 4.6.3 con la optimización de O2, el código de conjunto resultante es:

9 0000 83EC1C    subl $28, %esp 
    11 0003 DD050000    fldl .LC0 
    12 0009 DD1C24    fstpl (%esp) 
    13 000c E8FCFFFF    call _Z1fd 
    14 0011 83C41C    addl $28, %esp 
    16 0014 C3     ret 
    73     .LC0: 
    74 0000 6412264A    .long 1244009060 
    75 0004 47EC1940    .long 1075440711 

La función sqrt Nunca se llama en realidad, y el valor simplemente se almacena como parte del programa.

en consecuencia, crear una función que técnicamente se adapte a sus necesidades, sólo tiene que necesitaría:

template<unsigned int N> inline double meta_sqrt() { return sqrt(N); } 

Answer 2

El problema que veo es que metaP efectivamente usa las enumeraciones en las variables. El problema es que las enumeraciones se tratan internamente como enteros, lo que impide tratar de obtener un valor de coma flotante. Sin embargo, puede crear su propio formato de punto flotante que crea dos resultados, una parte entera y un exponente. Aún tendrá que procesar esto en un flotador, como Out = Sqrt<42>::mantissa * pow(10,Sqrt<42>::exponent);. En realidad, la determinación de los valores se deja como un ejercicio para el lector, pero probablemente tendrá que escalar la entrada hacia arriba (con un poder par de 10), calcular la raíz y almacenar el poder/2 que utilizó anteriormente.

Para calcular sqrt < 42>, primero debe establecer el exponente enum a una potencia adecuada, como '-4' (cuanto más bajo, más decimales, pero observe si hay desbordamiento). A continuación, multiplica la entrada por '10^(- 2 * exponente) '. En este caso obtienes 42 * 10^8 = 4200000000. Luego tomas la raíz de este valor obteniendo '64807' como el valor final. En tiempo de ejecución, calcula el "val * 10^exponente" = "64807 * 10^-4" = 64807 * 0.0001 = 6.4807m y lo almacena en un flotador.

El trabajo de conversión excede el propósito, pero puede reducirlo almacenando el exponente como 10^k (es decir, 10^4) y luego haciendo out=sqrt<x>::mantissa/sqrt<x>::exponent.

edit Acabo de notar que con el método mantissa/exponente, la elección del exponente es arbitraria siempre que sea más grande que la parte entera de la raíz final. Incluso puede ser una constante, lo que facilita el diseño de sus metafunciones. En el caso de 42, por ejemplo, puede seleccionar el 'exponente' para que siempre sea 6000. Luego, multiplica la entrada por 6000^2, toma la raíz entera del producto, luego, en tiempo de ejecución, divide el resultado por 6000 para obtener la raíz . En lugar de tratar la salida como a * 10^b, utiliza la relación sqr (x * b^2) = sqr (x) * b. La matemática desprotege:

• 42 * 6000 * 6000 = 1512000000
• SQR (1512000000) = 38884
• 38884/6000 = 6,4806 (al cuadrado es 41,999)

Answer 3

Eigen contiene este meta_sqrt que utiliza búsqueda binaria:

template<int Y, 
     int InfX = 0, 
     int SupX = ((Y==1) ? 1 : Y/2), 
     bool Done = ((SupX-InfX)<=1 ? true : ((SupX*SupX <= Y) && ((SupX+1)*(SupX+1) > Y))) > 
           // use ?: instead of || just to shut up a stupid gcc 4.3 warning 
class meta_sqrt 
{ 
    enum { 
    MidX = (InfX+SupX)/2, 
    TakeInf = MidX*MidX > Y ? 1 : 0, 
    NewInf = int(TakeInf) ? InfX : int(MidX), 
    NewSup = int(TakeInf) ? int(MidX) : SupX 
}; 
    public: 
    enum { ret = meta_sqrt<Y,NewInf,NewSup>::ret }; 
}; 

template<int Y, int InfX, int SupX> 
class meta_sqrt<Y, InfX, SupX, true> 
{ 
    public: enum { ret = (SupX*SupX <= Y) ? SupX : InfX }; 
};