Debian Codegraph @

src/Imath/ImathRoots.h

raw
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