ceph/src/boost/boost/math/tools/quartic_roots.hpp

   1 //  (C) Copyright Nick Thompson 2021.
   2 //  Use, modification and distribution are subject to the
   3 //  Boost Software License, Version 1.0. (See accompanying file
   4 //  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 #ifndef BOOST_MATH_TOOLS_QUARTIC_ROOTS_HPP
   6 #define BOOST_MATH_TOOLS_QUARTIC_ROOTS_HPP
   7 #include <array>
   8 #include <cmath>
   9 #include <boost/math/tools/cubic_roots.hpp>
  10
  11 namespace boost::math::tools {
  12
  13 namespace detail {
  14
  15 // Make sure the nans are always at the back of the array:
  16 template<typename Real>
  17 bool comparator(Real r1, Real r2) {
  18    using std::isnan;
  19    if (isnan(r1)) { return false; }
  20    if (isnan(r2)) { return true; }
  21    return r1 < r2;
  22 }
  23
  24 template<typename Real>
  25 std::array<Real, 4> polish_and_sort(Real a, Real b, Real c, Real d, Real e, std::array<Real, 4>& roots) {
  26     // Polish the roots with a Halley iterate.
  27     using std::fma;
  28     using std::abs;
  29     for (auto &r : roots) {
  30         Real df = fma(4*a, r, 3*b);
  31         df = fma(df, r, 2*c);
  32         df = fma(df, r, d);
  33         Real d2f = fma(12*a, r, 6*b);
  34         d2f = fma(d2f, r, 2*c);
  35         Real f = fma(a, r, b);
  36         f = fma(f,r,c);
  37         f = fma(f,r,d);
  38         f = fma(f,r,e);
  39         Real denom = 2*df*df - f*d2f;
  40         if (abs(denom) > (std::numeric_limits<Real>::min)())
  41         {
  42             r -= 2*f*df/denom;
  43         }
  44     }
  45     std::sort(roots.begin(), roots.end(), detail::comparator<Real>);
  46     return roots;
  47 }
  48
  49 }
  50 // Solves ax^4 + bx^3 + cx^2 + dx + e = 0.
  51 // Only returns the real roots, as these are the only roots of interest in ray intersection problems.
  52 // Follows Graphics Gems V: https://github.com/erich666/GraphicsGems/blob/master/gems/Roots3And4.c
  53 template<typename Real>
  54 std::array<Real, 4> quartic_roots(Real a, Real b, Real c, Real d, Real e) {
  55     using std::abs;
  56     using std::sqrt;
  57     auto nan = std::numeric_limits<Real>::quiet_NaN();
  58     std::array<Real, 4> roots{nan, nan, nan, nan};
  59     if (abs(a) <= (std::numeric_limits<Real>::min)()) {
  60         auto cbrts = cubic_roots(b, c, d, e);
  61         roots[0] = cbrts[0];
  62         roots[1] = cbrts[1];
  63         roots[2] = cbrts[2];
  64         if (b == 0 && c == 0 && d == 0 && e == 0) {
  65            roots[3] = 0;
  66         }
  67         return detail::polish_and_sort(a, b, c, d, e, roots);
  68     }
  69     if (abs(e) <= (std::numeric_limits<Real>::min)()) {
  70         auto v = cubic_roots(a, b, c, d);
  71         roots[0] = v[0];
  72         roots[1] = v[1];
  73         roots[2] = v[2];
  74         roots[3] = 0;
  75         return detail::polish_and_sort(a, b, c, d, e, roots);
  76     }
  77     // Now solve x^4 + Ax^3 + Bx^2 + Cx + D = 0.
  78     Real A = b/a;
  79     Real B = c/a;
  80     Real C = d/a;
  81     Real D = e/a;
  82     Real Asq = A*A;
  83     // Let x = y - A/4:
  84     // Mathematica: Expand[(y - A/4)^4 + A*(y - A/4)^3 + B*(y - A/4)^2 + C*(y - A/4) + D]
  85     // We now solve the depressed quartic y^4 + py^2 + qy + r = 0.
  86     Real p = B - 3*Asq/8;
  87     Real q = C - A*B/2 + Asq*A/8;
  88     Real r = D - A*C/4 + Asq*B/16 - 3*Asq*Asq/256;
  89     if (abs(r) <= (std::numeric_limits<Real>::min)()) {
  90         auto [r1, r2, r3] = cubic_roots(Real(1), Real(0), p, q);
  91         r1 -= A/4;
  92         r2 -= A/4;
  93         r3 -= A/4;
  94         roots[0] = r1;
  95         roots[1] = r2;
  96         roots[2] = r3;
  97         roots[3] = -A/4;
  98         return detail::polish_and_sort(a, b, c, d, e, roots);
  99     }
 100     // Biquadratic case:
 101     if (abs(q) <= (std::numeric_limits<Real>::min)()) {
 102         auto [r1, r2] = quadratic_roots(Real(1), p, r);
 103         if (r1 >= 0) {
 104            Real rtr = sqrt(r1);
 105            roots[0] = rtr - A/4;
 106            roots[1] = -rtr - A/4;
 107         }
 108         if (r2 >= 0) {
 109            Real rtr = sqrt(r2);
 110            roots[2] = rtr - A/4;
 111            roots[3] = -rtr - A/4;
 112         }
 113         return detail::polish_and_sort(a, b, c, d, e, roots);
 114     }
 115
 116     // Now split the depressed quartic into two quadratics:
 117     // y^4 + py^2 + qy + r = (y^2 + sy + u)(y^2 - sy + v) = y^4 + (v+u-s^2)y^2 + s(v - u)y + uv
 118     // So p = v+u-s^2, q = s(v - u), r = uv.
 119     // Then (v+u)^2 - (v-u)^2 = 4uv = 4r = (p+s^2)^2 - q^2/s^2.
 120     // Multiply through by s^2 to get s^2(p+s^2)^2 - q^2 - 4rs^2 = 0, which is a cubic in s^2.
 121     // Then we let z = s^2, to get
 122     // z^3 + 2pz^2 + (p^2 - 4r)z - q^2 = 0.
 123     auto z_roots = cubic_roots(Real(1), 2*p, p*p - 4*r, -q*q);
 124     // z = s^2, so s = sqrt(z).
 125     // No real roots:
 126     if (z_roots.back() <= 0) {
 127       return roots;
 128     }
 129     Real s = sqrt(z_roots.back());
 130
 131     // s is nonzero, because we took care of the biquadratic case.
 132     Real v = (p + s*s + q/s)/2;
 133     Real u = v - q/s;
 134     // Now solve y^2 + sy + u = 0:
 135     auto [root0, root1] = quadratic_roots(Real(1), s, u);
 136
 137     // Now solve y^2 - sy + v = 0:
 138     auto [root2, root3] = quadratic_roots(Real(1), -s, v);
 139     roots[0] = root0;
 140     roots[1] = root1;
 141     roots[2] = root2;
 142     roots[3] = root3;
 143
 144     for (auto& r : roots) {
 145         r -= A/4;
 146     }
 147     return detail::polish_and_sort(a, b, c, d, e, roots);
 148 }
 149
 150 }
 151 #endif