| 1 |
// |
| 2 |
// SPDX-License-Identifier: BSD-3-Clause |
| 3 |
// Copyright Contributors to the OpenEXR Project. |
| 4 |
// |
| 5 |
|
| 6 |
// |
| 7 |
// Functions to solve linear, quadratic or cubic equations |
| 8 |
// |
| 9 |
// Note: It is possible that an equation has real solutions, but that |
| 10 |
// the solutions (or some intermediate result) are not representable. |
| 11 |
// In this case, either some of the solutions returned are invalid |
| 12 |
// (nan or infinity), or, if floating-point exceptions have been |
| 13 |
// enabled, an exception is thrown. |
| 14 |
// |
| 15 |
|
| 16 |
#ifndef INCLUDED_IMATHROOTS_H |
| 17 |
#define INCLUDED_IMATHROOTS_H |
| 18 |
|
| 19 |
#include "ImathMath.h" |
| 20 |
#include "ImathNamespace.h" |
| 21 |
#include <complex> |
| 22 |
|
| 23 |
/// @cond Doxygen_Suppress |
| 24 |
|
| 25 |
#ifdef __CUDACC__ |
| 26 |
# include <thrust/complex.h> |
| 27 |
# define COMPLEX_NAMESPACE thrust |
| 28 |
#else |
| 29 |
# define COMPLEX_NAMESPACE std |
| 30 |
#endif |
| 31 |
|
| 32 |
/// @endcond |
| 33 |
|
| 34 |
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER |
| 35 |
|
| 36 |
/// |
| 37 |
/// Solve for x in the linear equation: |
| 38 |
/// |
| 39 |
/// a * x + b == 0 |
| 40 |
/// |
| 41 |
/// @return 1 if the equation has a solution, 0 if there is no |
| 42 |
/// solution, and -1 if all real numbers are solutions. |
| 43 |
template <class T> IMATH_HOSTDEVICE IMATH_CONSTEXPR14 int solveLinear (T a, T b, T& x); |
| 44 |
|
| 45 |
/// |
| 46 |
/// Solve for x in the quadratic equation: |
| 47 |
/// |
| 48 |
/// a * x*x + b * x + c == 0 |
| 49 |
/// |
| 50 |
/// @return 2 if the equation has two solutions, 1 if the equation has |
| 51 |
/// a single solution, 0 if there is no solution, and -1 if all real |
| 52 |
/// numbers are solutions. |
| 53 |
template <class T> IMATH_HOSTDEVICE IMATH_CONSTEXPR14 int solveQuadratic (T a, T b, T c, T x[2]); |
| 54 |
template <class T> |
| 55 |
|
| 56 |
/// |
| 57 |
/// Solve for x in the normalized cubic equation: |
| 58 |
/// |
| 59 |
/// x*x*x + r * x*x + s * x + t == 0 |
| 60 |
/// |
| 61 |
/// The equation is solved using Cardano's Formula; even though only |
| 62 |
/// real solutions are produced, some intermediate results are complex |
| 63 |
/// (std::complex<T>). |
| 64 |
/// |
| 65 |
/// @return 0 if there is no solution, and -1 if all real |
| 66 |
/// numbers are solutions, otherwise return the number of solutions. |
| 67 |
IMATH_HOSTDEVICE IMATH_CONSTEXPR14 int solveNormalizedCubic (T r, T s, T t, T x[3]); |
| 68 |
|
| 69 |
/// |
| 70 |
/// Solve for x in the cubic equation: |
| 71 |
/// |
| 72 |
/// a * x*x*x + b * x*x + c * x + d == 0 |
| 73 |
/// |
| 74 |
/// The equation is solved using Cardano's Formula; even though only |
| 75 |
/// real solutions are produced, some intermediate results are complex |
| 76 |
/// (std::complex<T>). |
| 77 |
/// |
| 78 |
/// @return 0 if there is no solution, and -1 if all real |
| 79 |
/// numbers are solutions, otherwise return the number of solutions. |
| 80 |
template <class T> IMATH_HOSTDEVICE IMATH_CONSTEXPR14 int solveCubic (T a, T b, T c, T d, T x[3]); |
| 81 |
|
| 82 |
//--------------- |
| 83 |
// Implementation |
| 84 |
//--------------- |
| 85 |
|
| 86 |
template <class T> |
| 87 |
IMATH_CONSTEXPR14 int |
| 88 |
solveLinear (T a, T b, T& x) |
| 89 |
{ |
| 90 |
if (a != 0) |
| 91 |
{ |
| 92 |
x = -b / a; |
| 93 |
return 1; |
| 94 |
} |
| 95 |
else if (b != 0) |
| 96 |
{ |
| 97 |
return 0; |
| 98 |
} |
| 99 |
else |
| 100 |
{ |
| 101 |
return -1; |
| 102 |
} |
| 103 |
} |
| 104 |
|
| 105 |
template <class T> |
| 106 |
IMATH_CONSTEXPR14 int |
| 107 |
solveQuadratic (T a, T b, T c, T x[2]) |
| 108 |
{ |
| 109 |
if (a == 0) |
| 110 |
{ |
| 111 |
return solveLinear (b, c, x[0]); |
| 112 |
} |
| 113 |
else |
| 114 |
{ |
| 115 |
T D = b * b - 4 * a * c; |
| 116 |
|
| 117 |
if (D > 0) |
| 118 |
{ |
| 119 |
T s = std::sqrt (D); |
| 120 |
T q = -(b + (b > 0 ? 1 : -1) * s) / T (2); |
| 121 |
|
| 122 |
x[0] = q / a; |
| 123 |
x[1] = c / q; |
| 124 |
return 2; |
| 125 |
} |
| 126 |
if (D == 0) |
| 127 |
{ |
| 128 |
x[0] = -b / (2 * a); |
| 129 |
return 1; |
| 130 |
} |
| 131 |
else |
| 132 |
{ |
| 133 |
return 0; |
| 134 |
} |
| 135 |
} |
| 136 |
} |
| 137 |
|
| 138 |
template <class T> |
| 139 |
IMATH_CONSTEXPR14 int |
| 140 |
solveNormalizedCubic (T r, T s, T t, T x[3]) |
| 141 |
{ |
| 142 |
T p = (3 * s - r * r) / 3; |
| 143 |
T q = 2 * r * r * r / 27 - r * s / 3 + t; |
| 144 |
T p3 = p / 3; |
| 145 |
T q2 = q / 2; |
| 146 |
T D = p3 * p3 * p3 + q2 * q2; |
| 147 |
|
| 148 |
if (D == 0 && p3 == 0) |
| 149 |
{ |
| 150 |
x[0] = -r / 3; |
| 151 |
x[1] = -r / 3; |
| 152 |
x[2] = -r / 3; |
| 153 |
return 1; |
| 154 |
} |
| 155 |
|
| 156 |
if (D > 0) |
| 157 |
{ |
| 158 |
auto real_root = [] (T a, T x) -> T { |
| 159 |
T sign = std::copysign(T(1), a); |
| 160 |
return sign * std::pow (sign * a, T (1) / x); |
| 161 |
}; |
| 162 |
|
| 163 |
T u = real_root (-q / 2 + std::sqrt (D), 3); |
| 164 |
T v = -p / (T (3) * u); |
| 165 |
|
| 166 |
x[0] = u + v - r / 3; |
| 167 |
return 1; |
| 168 |
} |
| 169 |
|
| 170 |
namespace CN = COMPLEX_NAMESPACE; |
| 171 |
CN::complex<T> u = CN::pow (-q / 2 + CN::sqrt (CN::complex<T> (D)), T (1) / T (3)); |
| 172 |
CN::complex<T> v = -p / (T (3) * u); |
| 173 |
|
| 174 |
const T sqrt3 = T (1.73205080756887729352744634150587); // enough digits |
| 175 |
// for long double |
| 176 |
CN::complex<T> y0 (u + v); |
| 177 |
CN::complex<T> y1 (-(u + v) / T (2) + (u - v) / T (2) * CN::complex<T> (0, sqrt3)); |
| 178 |
CN::complex<T> y2 (-(u + v) / T (2) - (u - v) / T (2) * CN::complex<T> (0, sqrt3)); |
| 179 |
|
| 180 |
if (D == 0) |
| 181 |
{ |
| 182 |
x[0] = y0.real() - r / 3; |
| 183 |
x[1] = y1.real() - r / 3; |
| 184 |
return 2; |
| 185 |
} |
| 186 |
else |
| 187 |
{ |
| 188 |
x[0] = y0.real() - r / 3; |
| 189 |
x[1] = y1.real() - r / 3; |
| 190 |
x[2] = y2.real() - r / 3; |
| 191 |
return 3; |
| 192 |
} |
| 193 |
} |
| 194 |
|
| 195 |
template <class T> |
| 196 |
IMATH_CONSTEXPR14 int |
| 197 |
solveCubic (T a, T b, T c, T d, T x[3]) |
| 198 |
{ |
| 199 |
if (a == 0) |
| 200 |
{ |
| 201 |
return solveQuadratic (b, c, d, x); |
| 202 |
} |
| 203 |
else |
| 204 |
{ |
| 205 |
return solveNormalizedCubic (b / a, c / a, d / a, x); |
| 206 |
} |
| 207 |
} |
| 208 |
|
| 209 |
IMATH_INTERNAL_NAMESPACE_HEADER_EXIT |
| 210 |
|
| 211 |
#endif // INCLUDED_IMATHROOTS_H |