qualia_core_db/solvers/calculus/
quadrature.rs1#[derive(Debug, Clone, Copy, PartialEq)]
4pub enum QuadratureError {
5 InvalidDomain,
6 NonFiniteIntegrand { x: f64 },
7 EvaluationBudgetExceeded,
8 WorkspaceExceeded,
9}
10
11#[repr(C)]
12#[derive(Debug, Clone, Copy, PartialEq)]
13pub struct QuadratureResult {
14 pub value: f64,
15 pub absolute_error: f64,
16 pub evaluations: u32,
17 pub intervals: u32,
18}
19
20#[derive(Clone, Copy, Default)]
21struct SimpsonPanel {
22 a: f64,
23 b: f64,
24 fa: f64,
25 fm: f64,
26 fb: f64,
27 whole: f64,
28 tolerance: f64,
29}
30
31const MAX_ADAPTIVE_PANELS: usize = 512;
32
33fn checked_eval<F>(function: &F, x: f64) -> Result<f64, QuadratureError>
34where
35 F: Fn(f64) -> f64,
36{
37 let value = function(x);
38 if value.is_finite() {
39 Ok(value)
40 } else {
41 Err(QuadratureError::NonFiniteIntegrand { x })
42 }
43}
44
45pub fn adaptive_simpson<F>(
47 function: F,
48 a: f64,
49 b: f64,
50 absolute_tolerance: f64,
51 max_evaluations: u32,
52) -> Result<QuadratureResult, QuadratureError>
53where
54 F: Fn(f64) -> f64,
55{
56 if !a.is_finite()
57 || !b.is_finite()
58 || b <= a
59 || !absolute_tolerance.is_finite()
60 || absolute_tolerance <= 0.0
61 || max_evaluations < 3
62 {
63 return Err(QuadratureError::InvalidDomain);
64 }
65
66 let midpoint = 0.5 * (a + b);
67 let fa = checked_eval(&function, a)?;
68 let fm = checked_eval(&function, midpoint)?;
69 let fb = checked_eval(&function, b)?;
70 let whole = (b - a) * (fa + 4.0 * fm + fb) / 6.0;
71 let mut evaluations = 3_u32;
72 let mut stack = [SimpsonPanel::default(); MAX_ADAPTIVE_PANELS];
73 stack[0] = SimpsonPanel {
74 a,
75 b,
76 fa,
77 fm,
78 fb,
79 whole,
80 tolerance: absolute_tolerance,
81 };
82 let mut stack_len = 1;
83 let mut value = 0.0;
84 let mut error = 0.0;
85 let mut intervals = 0;
86
87 while stack_len > 0 {
88 stack_len -= 1;
89 let panel = stack[stack_len];
90 if evaluations + 2 > max_evaluations {
91 return Err(QuadratureError::EvaluationBudgetExceeded);
92 }
93 let midpoint = 0.5 * (panel.a + panel.b);
94 let left_midpoint = 0.5 * (panel.a + midpoint);
95 let right_midpoint = 0.5 * (midpoint + panel.b);
96 let flm = checked_eval(&function, left_midpoint)?;
97 let frm = checked_eval(&function, right_midpoint)?;
98 evaluations += 2;
99
100 let left = (midpoint - panel.a) * (panel.fa + 4.0 * flm + panel.fm) / 6.0;
101 let right = (panel.b - midpoint) * (panel.fm + 4.0 * frm + panel.fb) / 6.0;
102 let delta = left + right - panel.whole;
103 let local_error = delta.abs() / 15.0;
104 if local_error <= panel.tolerance {
105 value += left + right + delta / 15.0;
106 error += local_error;
107 intervals += 2;
108 continue;
109 }
110
111 if stack_len + 2 > stack.len() {
112 return Err(QuadratureError::WorkspaceExceeded);
113 }
114 let child_tolerance = panel.tolerance * 0.5;
115 stack[stack_len] = SimpsonPanel {
116 a: midpoint,
117 b: panel.b,
118 fa: panel.fm,
119 fm: frm,
120 fb: panel.fb,
121 whole: right,
122 tolerance: child_tolerance,
123 };
124 stack[stack_len + 1] = SimpsonPanel {
125 a: panel.a,
126 b: midpoint,
127 fa: panel.fa,
128 fm: flm,
129 fb: panel.fm,
130 whole: left,
131 tolerance: child_tolerance,
132 };
133 stack_len += 2;
134 }
135
136 Ok(QuadratureResult {
137 value,
138 absolute_error: error,
139 evaluations,
140 intervals,
141 })
142}
143
144const GK15_ABSCISSAE: [f64; 8] = [
145 0.991_455_371_120_812_6,
146 0.949_107_912_342_758_5,
147 0.864_864_423_359_769_1,
148 0.741_531_185_599_394_5,
149 0.586_087_235_467_691_1,
150 0.405_845_151_377_397_2,
151 0.207_784_955_007_898_48,
152 0.0,
153];
154const GK15_WEIGHTS: [f64; 8] = [
155 0.022_935_322_010_529_224,
156 0.063_092_092_629_978_55,
157 0.104_790_010_322_250_19,
158 0.140_653_259_715_525_92,
159 0.169_004_726_639_267_9,
160 0.190_350_578_064_785_42,
161 0.204_432_940_075_298_89,
162 0.209_482_141_084_727_82,
163];
164const G7_WEIGHTS: [f64; 4] = [
165 0.129_484_966_168_869_7,
166 0.279_705_391_489_276_64,
167 0.381_830_050_505_118_9,
168 0.417_959_183_673_469_4,
169];
170
171#[derive(Clone, Copy, Default)]
172struct IntervalPanel {
173 a: f64,
174 b: f64,
175 tolerance: f64,
176}
177
178fn gauss_kronrod_15_panel<F>(
179 function: &F,
180 a: f64,
181 b: f64,
182) -> Result<(f64, f64, u32), QuadratureError>
183where
184 F: Fn(f64) -> f64,
185{
186 let center = 0.5 * (a + b);
187 let half = 0.5 * (b - a);
188 let center_value = checked_eval(function, center)?;
189 let mut kronrod = GK15_WEIGHTS[7] * center_value;
190 let mut gauss = G7_WEIGHTS[3] * center_value;
191
192 for index in 0..7 {
193 let offset = half * GK15_ABSCISSAE[index];
194 let pair =
195 checked_eval(function, center - offset)? + checked_eval(function, center + offset)?;
196 kronrod += GK15_WEIGHTS[index] * pair;
197 match index {
198 1 => gauss += G7_WEIGHTS[0] * pair,
199 3 => gauss += G7_WEIGHTS[1] * pair,
200 5 => gauss += G7_WEIGHTS[2] * pair,
201 _ => {}
202 }
203 }
204 let kronrod = kronrod * half;
205 let gauss = gauss * half;
206 Ok((kronrod, (kronrod - gauss).abs(), 15))
207}
208
209pub fn adaptive_gauss_kronrod_15<F>(
211 function: F,
212 a: f64,
213 b: f64,
214 absolute_tolerance: f64,
215 max_evaluations: u32,
216) -> Result<QuadratureResult, QuadratureError>
217where
218 F: Fn(f64) -> f64,
219{
220 if !a.is_finite()
221 || !b.is_finite()
222 || b <= a
223 || !absolute_tolerance.is_finite()
224 || absolute_tolerance <= 0.0
225 || max_evaluations < 15
226 {
227 return Err(QuadratureError::InvalidDomain);
228 }
229
230 let mut stack = [IntervalPanel::default(); MAX_ADAPTIVE_PANELS];
231 stack[0] = IntervalPanel {
232 a,
233 b,
234 tolerance: absolute_tolerance,
235 };
236 let mut stack_len = 1;
237 let mut evaluations = 0;
238 let mut intervals = 0;
239 let mut value = 0.0;
240 let mut error = 0.0;
241
242 while stack_len > 0 {
243 stack_len -= 1;
244 let panel = stack[stack_len];
245 if evaluations + 15 > max_evaluations {
246 return Err(QuadratureError::EvaluationBudgetExceeded);
247 }
248 let (estimate, local_error, used) = gauss_kronrod_15_panel(&function, panel.a, panel.b)?;
249 evaluations += used;
250 if local_error <= panel.tolerance {
251 value += estimate;
252 error += local_error;
253 intervals += 1;
254 continue;
255 }
256 if stack_len + 2 > stack.len() {
257 return Err(QuadratureError::WorkspaceExceeded);
258 }
259 let midpoint = 0.5 * (panel.a + panel.b);
260 let tolerance = panel.tolerance * 0.5;
261 stack[stack_len] = IntervalPanel {
262 a: midpoint,
263 b: panel.b,
264 tolerance,
265 };
266 stack[stack_len + 1] = IntervalPanel {
267 a: panel.a,
268 b: midpoint,
269 tolerance,
270 };
271 stack_len += 2;
272 }
273
274 Ok(QuadratureResult {
275 value,
276 absolute_error: error,
277 evaluations,
278 intervals,
279 })
280}
281
282#[cfg(test)]
283mod tests {
284 use super::*;
285
286 #[test]
287 fn adaptive_simpson_meets_tolerance_and_reports_budget_failure() {
288 let result =
289 adaptive_simpson(|x| x.sin(), 0.0, core::f64::consts::PI, 1e-12, 10_000).unwrap();
290 assert!((result.value - 2.0).abs() < 1e-12);
291 assert!(result.absolute_error < 1e-12);
292 assert_eq!(
293 adaptive_simpson(|x| x.sin(), 0.0, 1.0, 1e-14, 3),
294 Err(QuadratureError::EvaluationBudgetExceeded)
295 );
296 }
297
298 #[test]
299 fn gauss_kronrod_integrates_polynomial_and_oscillation() {
300 let polynomial =
301 adaptive_gauss_kronrod_15(|x| x.powi(12), 0.0, 1.0, 1e-13, 10_000).unwrap();
302 assert!((polynomial.value - 1.0 / 13.0).abs() < 1e-13);
303
304 let oscillatory =
305 adaptive_gauss_kronrod_15(|x| (50.0 * x).sin(), 0.0, 1.0, 1e-10, 50_000).unwrap();
306 let expected = (1.0 - 50.0_f64.cos()) / 50.0;
307 assert!((oscillatory.value - expected).abs() < 1e-10);
308 }
309
310 #[test]
311 fn quadrature_rejects_reversed_and_non_finite_domains() {
312 assert_eq!(
313 adaptive_simpson(|x| x, 1.0, 0.0, 1e-6, 100),
314 Err(QuadratureError::InvalidDomain)
315 );
316 assert!(matches!(
317 adaptive_simpson(|x| if x > 0.4 { f64::NAN } else { x }, 0.0, 1.0, 1e-6, 100),
318 Err(QuadratureError::NonFiniteIntegrand { .. })
319 ));
320 }
321}