Jason Hise wrote:
I was just playing around, trying to compute a square root at compile time. I came up with the following:
template < unsigned int N, unsigned int X = 1, unsigned int X2 = ( X + N / X ) / 2 > struct Sqrt { typedef typename Sqrt < N, X2 > :: ValueHolder ValueHolder; };
template < unsigned int N, unsigned int X > struct Sqrt < N, X, X > { struct ValueHolder { enum ValueStorage { Value = X }; }; };
This works for most values, but unfortunately some ( like 80 ) end up oscillating and X never becomes equal to X2. How could I go about correcting this?
// This is a somewhat boostified implementation // of your algorithm rotated by 180 degrees 8-) #include <boost/config.hpp> #include <boost/mpl/eval_if.hpp> #include <boost/mpl/identity.hpp> using namespace boost::mpl; template< unsigned int N> struct sqrt_result { BOOST_STATIC_CONSTANT(unsigned int, value = N); }; template< unsigned int N, unsigned int I > struct sqrt_impl { // Note: Bare ICEs ( '(I*I>N)', '(I+N/I)/2' ) are not very portable // [ ref. http://www.boost.org/more/int_const_guidelines.htm ]. // Using separate metafunctions (like sqrt_iteration_invariant, // sqrt_approximation_step) can solve the problem. typedef typename eval_if_c< (I*I>N) // approximation from above , sqrt_impl< N, (I+N/I)/2 > // step (original formula) , identity< sqrt_result<I> > >::type type; }; template< unsigned int N > struct sqrt : sqrt_impl<N,N>::type // start with I=N { // Note: Inheritance of static constants does not work properly for // all compilers. An explicit advice like: // // typedef typename sqrt_impl<N,N>::type base; // using base::value // // may solve this problem. typedef sqrt type; }; // Test #include <iostream> using namespace std; template< unsigned int N > void test() { cout << "sqrt(" << N << ") = " << ::sqrt< N >::value << std::endl; } int main() { test< 1>(); test< 2>(); test< 3>(); test< 4>(); test< 9>(); test< 16>(); test< 80>(); test< 81>(); test<144>(); return 0; } // Hey, that was fun. // // Regards, // // Tobias