Square root metaphor?

Question

Is it possible to calculate the square root of an integer with a metaphone with the following signature:

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

(or perhaps using the constexpr keyword, I don't know which is better). In this case, sqrt<2>() will be replaced by 1.414... at compile time.

What would be the best implementation for such a function?

Answer 1

Perhaps this is not what you are looking for, but I wanted to make sure that you understood that, as a rule, during optimization, the compiler still calculates the result at compile time. For example, if you have this code:

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

With g ++ 4.6.3 with -O2 optimization, the final build code is:

  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 

The sqrt function is never called, and the value is simply saved as part of the program.

Therefore, to create a function that technically meets your requirements, you just need:

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

Answer 2

Eigen contains this meta_sqrt , which uses a binary search:

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

Answer 3

The problem I see is that metaP effectively abuses enumerations in variables. The problem is that enumerations are processed internally as integers, which exclude an attempt to get a floating point value from them. However, you can create your own floating point format that creates two results, the integer part and the exponent. You still have to handle this in a float, like Out = Sqrt<42>::mantissa * pow(10,Sqrt<42>::exponent); . In fact, defining the values ​​remains as an exercise for the reader, but you will probably have to scale the input up (using uniform power of 10) by calculating the root and keeping the -power / 2 you used earlier.

To calculate sqrt <42>, you must first set the enumeration of exhibitors to a suitable capacity, for example, "-4" (lower, more decimal, but watch overflow). Then you multiply the input by '10 ^ (- 2 * exponent) '. In this case, you get 42 * 10 ^ 8 = 4200000000. Then you take the root of this value, getting "64807" as the final value. At run time, you calculate the value "val * 10 ^ exponent" = "64807 * 10 ^ -4" = 64807 * 0.0001 = 6.4807m and save it in the float.

The extra conversion work causes the target to fail, but you can slightly reduce it by saving the metric as 10 ^ k (i.e. 10 ^ 4), then doing out=sqrt<x>::mantissa/sqrt<x>::exponent .

edit I just noticed that using the mantissa / exponent method, the choice of an indicator is arbitrary as long as it is larger than the integer part of the final root. It can even be permanent, which makes it easier to develop your meta functions. For example, in case 42, you can choose “exponent” always 6000. Then you multiply the input by 6000 ^ 2, take the integer root of the product, then divide the result by 6000 to get the root, Instead of processing the output as a * 10 ^ b it uses the relation sqr (x * b ^ 2) = sqr (x) * b. Mathematics is checked:

• 42 * 6000 * 6000 = 1512000000
• SQR (1512000000) = 38884
• 38884/6000 = 6.4806 (square - 41.999)