// Copyright John Maddock 2015

// 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)

// Comparison of finding roots using TOMS748, Newton-Raphson, Halley & Schroder algorithms.
// Note that this file contains Quickbook mark-up as well as code
// and comments, don't change any of the special comment mark-ups!
// This program also writes files in Quickbook tables mark-up format.

#include <boost/cstdlib.hpp>
#include <boost/config.hpp>
#include <boost/array.hpp>
#include <boost/math/tools/roots.hpp>
#include <boost/math/special_functions/ellint_1.hpp>
#include <boost/math/special_functions/ellint_2.hpp>
template <class T>
struct cbrt_functor_noderiv
{
   //  cube root of x using only function - no derivatives.
   cbrt_functor_noderiv(T const& to_find_root_of) : a(to_find_root_of)
   { /* Constructor just stores value a to find root of. */
   }
   T operator()(T const& x)
   {
      T fx = x*x*x - a; // Difference (estimate x^3 - a).
      return fx;
   }
private:
   T a; // to be 'cube_rooted'.
};
//] [/root_finding_noderiv_1

template <class T>
boost::uintmax_t cbrt_noderiv(T x, T guess)
{
   // return cube root of x using bracket_and_solve (no derivatives).
   using namespace std;                          // Help ADL of std functions.
   using namespace boost::math::tools;           // For bracket_and_solve_root.

   T factor = 2;                                 // How big steps to take when searching.

   const boost::uintmax_t maxit = 20;            // Limit to maximum iterations.
   boost::uintmax_t it = maxit;                  // Initally our chosen max iterations, but updated with actual.
   bool is_rising = true;                        // So if result if guess^3 is too low, then try increasing guess.
   int digits = std::numeric_limits<T>::digits;  // Maximum possible binary digits accuracy for type T.
   // Some fraction of digits is used to control how accurate to try to make the result.
   int get_digits = digits - 3;                  // We have to have a non-zero interval at each step, so
   // maximum accuracy is digits - 1.  But we also have to
   // allow for inaccuracy in f(x), otherwise the last few
   // iterations just thrash around.
   eps_tolerance<T> tol(get_digits);             // Set the tolerance.
   bracket_and_solve_root(cbrt_functor_noderiv<T>(x), guess, factor, is_rising, tol, it);
   return it;
}

template <class T>
struct cbrt_functor_deriv
{ // Functor also returning 1st derivative.
   cbrt_functor_deriv(T const& to_find_root_of) : a(to_find_root_of)
   { // Constructor stores value a to find root of,
      // for example: calling cbrt_functor_deriv<T>(a) to use to get cube root of a.
   }
   std::pair<T, T> operator()(T const& x)
   {
      // Return both f(x) and f'(x).
      T fx = x*x*x - a;                // Difference (estimate x^3 - value).
      T dx = 3 * x*x;                 // 1st derivative = 3x^2.
      return std::make_pair(fx, dx);   // 'return' both fx and dx.
   }
private:
   T a;                               // Store value to be 'cube_rooted'.
};

template <class T>
boost::uintmax_t cbrt_deriv(T x, T guess)
{
   // return cube root of x using 1st derivative and Newton_Raphson.
   using namespace boost::math::tools;
   T min = guess / 100;                     // We don't really know what this should be!
   T max = guess * 100;                     // We don't really know what this should be!
   const int digits = std::numeric_limits<T>::digits;  // Maximum possible binary digits accuracy for type T.
   int get_digits = static_cast<int>(digits * 0.6);    // Accuracy doubles with each step, so stop when we have
   // just over half the digits correct.
   const boost::uintmax_t maxit = 20;
   boost::uintmax_t it = maxit;
   newton_raphson_iterate(cbrt_functor_deriv<T>(x), guess, min, max, get_digits, it);
   return it;
}

template <class T>
struct cbrt_functor_2deriv
{
   // Functor returning both 1st and 2nd derivatives.
   cbrt_functor_2deriv(T const& to_find_root_of) : a(to_find_root_of)
   { // Constructor stores value a to find root of, for example:
      // calling cbrt_functor_2deriv<T>(x) to get cube root of x,
   }
   std::tuple<T, T, T> operator()(T const& x)
   {
      // Return both f(x) and f'(x) and f''(x).
      T fx = x*x*x - a;                     // Difference (estimate x^3 - value).
      T dx = 3 * x*x;                       // 1st derivative = 3x^2.
      T d2x = 6 * x;                        // 2nd derivative = 6x.
      return std::make_tuple(fx, dx, d2x);  // 'return' fx, dx and d2x.
   }
private:
   T a; // to be 'cube_rooted'.
};

template <class T>
boost::uintmax_t cbrt_2deriv(T x, T guess)
{ 
   // return cube root of x using 1st and 2nd derivatives and Halley.
   //using namespace std;  // Help ADL of std functions.
   using namespace boost::math::tools;
   T min = guess / 100;                     // We don't really know what this should be!
   T max = guess * 100;                     // We don't really know what this should be!
   const int digits = std::numeric_limits<T>::digits;  // Maximum possible binary digits accuracy for type T.
   // digits used to control how accurate to try to make the result.
   int get_digits = static_cast<int>(digits * 0.4);    // Accuracy triples with each step, so stop when just
   // over one third of the digits are correct.
   boost::uintmax_t maxit = 20;
   halley_iterate(cbrt_functor_2deriv<T>(x), guess, min, max, get_digits, maxit);
   return maxit;
}

template <class T>
boost::uintmax_t cbrt_2deriv_s(T x, T guess)
{ 
   // return cube root of x using 1st and 2nd derivatives and Halley.
   //using namespace std;  // Help ADL of std functions.
   using namespace boost::math::tools;
   T min = guess / 100;                     // We don't really know what this should be!
   T max = guess * 100;                     // We don't really know what this should be!
   const int digits = std::numeric_limits<T>::digits;  // Maximum possible binary digits accuracy for type T.
   // digits used to control how accurate to try to make the result.
   int get_digits = static_cast<int>(digits * 0.4);    // Accuracy triples with each step, so stop when just
   // over one third of the digits are correct.
   boost::uintmax_t maxit = 20;
   schroder_iterate(cbrt_functor_2deriv<T>(x), guess, min, max, get_digits, maxit);
   return maxit;
}

template <typename T = double>
struct elliptic_root_functor_noderiv
{ 
   elliptic_root_functor_noderiv(T const& arc, T const& radius) : m_arc(arc), m_radius(radius)
   { // Constructor just stores value a to find root of.
   }
   T operator()(T const& x)
   {
      // return the difference between required arc-length, and the calculated arc-length for an
      // ellipse with radii m_radius and x:
      T a = (std::max)(m_radius, x);
      T b = (std::min)(m_radius, x);
      T k = sqrt(1 - b * b / (a * a));
      return 4 * a * boost::math::ellint_2(k) - m_arc;
   }
private:
   T m_arc;     // length of arc.
   T m_radius;  // one of the two radii of the ellipse
}; // template <class T> struct elliptic_root_functor_noderiv

template <class T = double>
boost::uintmax_t elliptic_root_noderiv(T radius, T arc, T guess)
{ // return the other radius of an ellipse, given one radii and the arc-length
   using namespace std;  // Help ADL of std functions.
   using namespace boost::math::tools; // For bracket_and_solve_root.

   T factor = 2;                       // How big steps to take when searching.

   const boost::uintmax_t maxit = 50;  // Limit to maximum iterations.
   boost::uintmax_t it = maxit;        // Initally our chosen max iterations, but updated with actual.
   bool is_rising = true;              // arc-length increases if one radii increases, so function is rising
   // Define a termination condition, stop when nearly all digits are correct, but allow for
   // the fact that we are returning a range, and must have some inaccuracy in the elliptic integral:
   eps_tolerance<T> tol(std::numeric_limits<T>::digits - 2);
   // Call bracket_and_solve_root to find the solution, note that this is a rising function:
   bracket_and_solve_root(elliptic_root_functor_noderiv<T>(arc, radius), guess, factor, is_rising, tol, it);
   return it;
} 

template <class T = double>
struct elliptic_root_functor_1deriv
{ // Functor also returning 1st derviative.
   BOOST_STATIC_ASSERT_MSG(boost::is_integral<T>::value == false, "Only floating-point type types can be used!");

   elliptic_root_functor_1deriv(T const& arc, T const& radius) : m_arc(arc), m_radius(radius)
   { // Constructor just stores value a to find root of.
   }
   std::pair<T, T> operator()(T const& x)
   {
      // Return the difference between required arc-length, and the calculated arc-length for an
      // ellipse with radii m_radius and x, plus it's derivative.
      // See http://www.wolframalpha.com/input/?i=d%2Fda+[4+*+a+*+EllipticE%281+-+b^2%2Fa^2%29]
      // We require two elliptic integral calls, but from these we can calculate both
      // the function and it's derivative:
      T a = (std::max)(m_radius, x);
      T b = (std::min)(m_radius, x);
      T a2 = a * a;
      T b2 = b * b;
      T k = sqrt(1 - b2 / a2);
      T Ek = boost::math::ellint_2(k);
      T Kk = boost::math::ellint_1(k);
      T fx = 4 * a * Ek - m_arc;
      T dfx = 4 * (a2 * Ek - b2 * Kk) / (a2 - b2);
      return std::make_pair(fx, dfx);
   }
private:
   T m_arc;     // length of arc.
   T m_radius;  // one of the two radii of the ellipse
};  // struct elliptic_root__functor_1deriv

template <class T = double>
boost::uintmax_t elliptic_root_1deriv(T radius, T arc, T guess)
{
   using namespace std;  // Help ADL of std functions.
   using namespace boost::math::tools; // For newton_raphson_iterate.

   BOOST_STATIC_ASSERT_MSG(boost::is_integral<T>::value == false, "Only floating-point type types can be used!");

   T min = 0;   // Minimum possible value is zero.
   T max = arc; // Maximum possible value is the arc length.

   // Accuracy doubles at each step, so stop when just over half of the digits are
   // correct, and rely on that step to polish off the remainder:
   int get_digits = static_cast<int>(std::numeric_limits<T>::digits * 0.6);
   const boost::uintmax_t maxit = 20;
   boost::uintmax_t it = maxit;
   newton_raphson_iterate(elliptic_root_functor_1deriv<T>(arc, radius), guess, min, max, get_digits, it);
   return it;
}

template <class T = double>
struct elliptic_root_functor_2deriv
{ // Functor returning both 1st and 2nd derivatives.
   BOOST_STATIC_ASSERT_MSG(boost::is_integral<T>::value == false, "Only floating-point type types can be used!");

   elliptic_root_functor_2deriv(T const& arc, T const& radius) : m_arc(arc), m_radius(radius) {}
   std::tuple<T, T, T> operator()(T const& x)
   {
      // Return the difference between required arc-length, and the calculated arc-length for an
      // ellipse with radii m_radius and x, plus it's derivative.
      // See http://www.wolframalpha.com/input/?i=d^2%2Fda^2+[4+*+a+*+EllipticE%281+-+b^2%2Fa^2%29]
      // for the second derivative.
      T a = (std::max)(m_radius, x);
      T b = (std::min)(m_radius, x);
      T a2 = a * a;
      T b2 = b * b;
      T k = sqrt(1 - b2 / a2);
      T Ek = boost::math::ellint_2(k);
      T Kk = boost::math::ellint_1(k);
      T fx = 4 * a * Ek - m_arc;
      T dfx = 4 * (a2 * Ek - b2 * Kk) / (a2 - b2);
      T dfx2 = 4 * b2 * ((a2 + b2) * Kk - 2 * a2 * Ek) / (a * (a2 - b2) * (a2 - b2));
      return std::make_tuple(fx, dfx, dfx2);
   }
private:
   T m_arc;     // length of arc.
   T m_radius;  // one of the two radii of the ellipse
};

template <class T = double>
boost::uintmax_t elliptic_root_2deriv(T radius, T arc, T guess)
{
   using namespace std;                // Help ADL of std functions.
   using namespace boost::math::tools; // For halley_iterate.

   BOOST_STATIC_ASSERT_MSG(boost::is_integral<T>::value == false, "Only floating-point type types can be used!");

   T min = 0;                                   // Minimum possible value is zero.
   T max = arc;                                 // radius can't be larger than the arc length.

   // Accuracy triples at each step, so stop when just over one-third of the digits
   // are correct, and the last iteration will polish off the remaining digits:
   int get_digits = static_cast<int>(std::numeric_limits<T>::digits * 0.4);
   const boost::uintmax_t maxit = 20;
   boost::uintmax_t it = maxit;
   halley_iterate(elliptic_root_functor_2deriv<T>(arc, radius), guess, min, max, get_digits, it);
   return it;
} // nth_2deriv Halley
//]
// Using 1st and 2nd derivatives using Schroder algorithm.

template <class T = double>
boost::uintmax_t elliptic_root_2deriv_s(T radius, T arc, T guess)
{ // return nth root of x using 1st and 2nd derivatives and Schroder.

   using namespace std;  // Help ADL of std functions.
   using namespace boost::math::tools; // For schroder_iterate.

   BOOST_STATIC_ASSERT_MSG(boost::is_integral<T>::value == false, "Only floating-point type types can be used!");

   T min = 0; // Minimum possible value is zero.
   T max = arc; // radius can't be larger than the arc length.

   int digits = std::numeric_limits<T>::digits; // Maximum possible binary digits accuracy for type T.
   int get_digits = static_cast<int>(digits * 0.4);
   const boost::uintmax_t maxit = 20;
   boost::uintmax_t it = maxit;
   schroder_iterate(elliptic_root_functor_2deriv<T>(arc, radius), guess, min, max, get_digits, it);
   return it;
} // T elliptic_root_2deriv_s Schroder


int main()
{
   try
   {
      double to_root = 500;
      double answer = 7.93700525984;

      std::cout << "[table\n"
         << "[[Initial Guess=][-500% ([approx]1.323)][-100% ([approx]3.97)][-50% ([approx]3.96)][-20% ([approx]6.35)][-10% ([approx]7.14)][-5% ([approx]7.54)]"
         "[5% ([approx]8.33)][10% ([approx]8.73)][20% ([approx]9.52)][50% ([approx]11.91)][100% ([approx]15.87)][500 ([approx]47.6)]]\n";
      std::cout << "[[bracket_and_solve_root]["
         << cbrt_noderiv(to_root, answer / 6)
         << "][" << cbrt_noderiv(to_root, answer / 2)
         << "][" << cbrt_noderiv(to_root, answer - answer * 0.5)
         << "][" << cbrt_noderiv(to_root, answer - answer * 0.2)
         << "][" << cbrt_noderiv(to_root, answer - answer * 0.1)
         << "][" << cbrt_noderiv(to_root, answer - answer * 0.05)
         << "][" << cbrt_noderiv(to_root, answer + answer * 0.05)
         << "][" << cbrt_noderiv(to_root, answer + answer * 0.1)
         << "][" << cbrt_noderiv(to_root, answer + answer * 0.2)
         << "][" << cbrt_noderiv(to_root, answer + answer * 0.5)
         << "][" << cbrt_noderiv(to_root, answer + answer)
         << "][" << cbrt_noderiv(to_root, answer + answer * 5) << "]]\n";

      std::cout << "[[newton_iterate]["
         << cbrt_deriv(to_root, answer / 6)
         << "][" << cbrt_deriv(to_root, answer / 2)
         << "][" << cbrt_deriv(to_root, answer - answer * 0.5)
         << "][" << cbrt_deriv(to_root, answer - answer * 0.2)
         << "][" << cbrt_deriv(to_root, answer - answer * 0.1)
         << "][" << cbrt_deriv(to_root, answer - answer * 0.05)
         << "][" << cbrt_deriv(to_root, answer + answer * 0.05)
         << "][" << cbrt_deriv(to_root, answer + answer * 0.1)
         << "][" << cbrt_deriv(to_root, answer + answer * 0.2)
         << "][" << cbrt_deriv(to_root, answer + answer * 0.5)
         << "][" << cbrt_deriv(to_root, answer + answer)
         << "][" << cbrt_deriv(to_root, answer + answer * 5) << "]]\n";

      std::cout << "[[halley_iterate]["
         << cbrt_2deriv(to_root, answer / 6)
         << "][" << cbrt_2deriv(to_root, answer / 2)
         << "][" << cbrt_2deriv(to_root, answer - answer * 0.5)
         << "][" << cbrt_2deriv(to_root, answer - answer * 0.2)
         << "][" << cbrt_2deriv(to_root, answer - answer * 0.1)
         << "][" << cbrt_2deriv(to_root, answer - answer * 0.05)
         << "][" << cbrt_2deriv(to_root, answer + answer * 0.05)
         << "][" << cbrt_2deriv(to_root, answer + answer * 0.1)
         << "][" << cbrt_2deriv(to_root, answer + answer * 0.2)
         << "][" << cbrt_2deriv(to_root, answer + answer * 0.5)
         << "][" << cbrt_2deriv(to_root, answer + answer)
         << "][" << cbrt_2deriv(to_root, answer + answer * 5) << "]]\n";

      std::cout << "[[schr'''&#xf6;'''der_iterate]["
         << cbrt_2deriv_s(to_root, answer / 6)
         << "][" << cbrt_2deriv_s(to_root, answer / 2)
         << "][" << cbrt_2deriv_s(to_root, answer - answer * 0.5)
         << "][" << cbrt_2deriv_s(to_root, answer - answer * 0.2)
         << "][" << cbrt_2deriv_s(to_root, answer - answer * 0.1)
         << "][" << cbrt_2deriv_s(to_root, answer - answer * 0.05)
         << "][" << cbrt_2deriv_s(to_root, answer + answer * 0.05)
         << "][" << cbrt_2deriv_s(to_root, answer + answer * 0.1)
         << "][" << cbrt_2deriv_s(to_root, answer + answer * 0.2)
         << "][" << cbrt_2deriv_s(to_root, answer + answer * 0.5)
         << "][" << cbrt_2deriv_s(to_root, answer + answer)
         << "][" << cbrt_2deriv_s(to_root, answer + answer * 5) << "]]\n]\n\n";


      double radius_a = 10;
      double arc_length = 500;
      double radius_b = 123.6216507967705;

      std::cout << std::setprecision(4) << "[table\n"
         << "[[Initial Guess=][-500% ([approx]" << radius_b / 6 << ")][-100% ([approx]" << radius_b / 2 << ")][-50% ([approx]"
         << radius_b - radius_b * 0.5 << ")][-20% ([approx]" << radius_b - radius_b * 0.2 << ")][-10% ([approx]" << radius_b - radius_b * 0.1 << ")][-5% ([approx]" << radius_b - radius_b * 0.05 << ")]"
         "[5% ([approx]" << radius_b + radius_b * 0.05 << ")][10% ([approx]" << radius_b + radius_b * 0.1 << ")][20% ([approx]" << radius_b + radius_b * 0.2 << ")][50% ([approx]" << radius_b + radius_b * 0.5 
         << ")][100% ([approx]" << radius_b + radius_b << ")][500 ([approx]" << radius_b + radius_b * 5 << ")]]\n";
      std::cout << "[[bracket_and_solve_root]["
         << elliptic_root_noderiv(radius_a, arc_length, radius_b / 6)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b / 2)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b - radius_b * 0.5)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b - radius_b * 0.2)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b - radius_b * 0.1)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b - radius_b * 0.05)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b * 0.05)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b * 0.1)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b * 0.2)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b * 0.5)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b)
         << "][" << elliptic_root_noderiv(radius_a, arc_length, radius_b + radius_b * 5) << "]]\n";

      std::cout << "[[newton_iterate]["
         << elliptic_root_1deriv(radius_a, arc_length, radius_b / 6)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b / 2)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b - radius_b * 0.5)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b - radius_b * 0.2)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b - radius_b * 0.1)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b - radius_b * 0.05)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b * 0.05)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b * 0.1)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b * 0.2)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b * 0.5)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b)
         << "][" << elliptic_root_1deriv(radius_a, arc_length, radius_b + radius_b * 5) << "]]\n";

      std::cout << "[[halley_iterate]["
         << elliptic_root_2deriv(radius_a, arc_length, radius_b / 6)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b / 2)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b - radius_b * 0.5)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b - radius_b * 0.2)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b - radius_b * 0.1)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b - radius_b * 0.05)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b * 0.05)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b * 0.1)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b * 0.2)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b * 0.5)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b)
         << "][" << elliptic_root_2deriv(radius_a, arc_length, radius_b + radius_b * 5) << "]]\n";

      std::cout << "[[schr'''&#xf6;'''der_iterate]["
         << elliptic_root_2deriv_s(radius_a, arc_length, radius_b / 6)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b / 2)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b - radius_b * 0.5)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b - radius_b * 0.2)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b - radius_b * 0.1)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b - radius_b * 0.05)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b * 0.05)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b * 0.1)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b * 0.2)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b * 0.5)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b)
         << "][" << elliptic_root_2deriv_s(radius_a, arc_length, radius_b + radius_b * 5) << "]]\n]\n\n";

      return boost::exit_success;
   }
   catch(std::exception ex)
   {
      std::cout << "exception thrown: " << ex.what() << std::endl;
      return boost::exit_failure;
   }
} // int main()