[boost] Re: Meta-math

From: Tobias Schwinger (tschwinger_at_[hidden])
Date: 2005-01-27 15:14:21

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