//  (C) Copyright John Maddock 2006.

//  Use, modification and distribution are subject to the

//  Boost Software License, Version 1.0. (See accompanying file

//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)



#ifndef BOOST_MATH_SF_CBRT_HPP

#define BOOST_MATH_SF_CBRT_HPP



#include <boost/math/tools/roots.hpp>

#include <boost/math/special_functions/math_fwd.hpp>



namespace boost{ namespace math{



namespace detail

{



   template <class T>

   struct cbrt_functor

   {

       cbrt_functor(T const& target) : a(target){}

       std::tr1::tuple<T, T, T> operator()(T const& z)

       {

         T sqr = z * z;

         return std::tr1::make_tuple(sqr * z - a, 3 * sqr, 6 * z);

       }

   private:

       T a;

   };



template <class T, class Policy>

T cbrt_imp(T z, const Policy&)

{

   BOOST_MATH_STD_USING

   int i_exp, sign(1);

   if(z < 0)

   {

      z = -z;

      sign = -sign;

   }

   if(z == 0)

      return 0;



   frexp(z, &i_exp);

   T min = static_cast<T>(ldexp(0.5, i_exp/3));

   T max = static_cast<T>(ldexp(2.0, i_exp/3));

   T guess = static_cast<T>(ldexp(1.0, i_exp/3));

   int digits = (policies::digits<T, Policy>()) / 2;

   return sign * tools::halley_iterate(detail::cbrt_functor<T>(z), guess, min, max, digits);

}



} // namespace detail



template <class T, class Policy>

inline typename tools::promote_args<T>::type cbrt(T z, const Policy& pol)

{

   typedef typename tools::promote_args<T>::type result_type;

   return detail::cbrt_imp(result_type(z), pol);

}



template <class T>

inline typename tools::promote_args<T>::type cbrt(T z)

{

   return cbrt(z, policies::policy<>());

}



} // namespace math

} // namespace boost



#endif // BOOST_MATH_SF_CBRT_HPP







