//  boost fixed_math.hpp header file  ----------------------------------------//

//  (C) Copyright Stephen Nutt 2002. Permission to copy, use, modify, sell
//  and distribute this software is granted provided this copyright
//  notice appears in all copies. This software is provided "as is" without
//  express or implied warranty, and with no claim as to its suitability for
//  any purpose.

//  See http://www.boost.org for most recent version including documentation.

//  Revision History
//   26 Sep 02  Initial version

#include "fixed_math.hpp"

namespace boost
{

template <typename IntegerType>
IntegerType FixedSqrt (
  IntegerType x,
  unsigned int fractionalBits)
{
  BOOST_STATIC_CONSTANT (int, digits = std::numeric_limits<IntegerType>::digits);

  IntegerType root = 0;
  IntegerType remainder = 0;
  for (int i = digits / 2 - fractionalBits; i ; --i)
  {
    remainder = (remainder << 2) | (x >> (digits - 2));
    x <<= 2;
    root <<= 1;
    IntegerType testDiv = root << 1;
    if (remainder > testDiv)
    {
      remainder -= testDiv + 1;
      ++root;
    }
  }
	
  return root;
}

template unsigned long FixedSqrt (unsigned long, unsigned int);

#ifndef BOOST_NO_INT64_T
template uintmax_t FixedSqrt (uintmax_t, unsigned int);
#endif

};