Skip to main content

qualia_core_db/solvers/calculus/
quadrature.rs

1//! Adaptive scalar quadrature with bounded, non-recursive work stacks.
2
3#[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
45/// Adaptive Simpson quadrature.
46pub 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
209/// Adaptive Gauss-Kronrod 15 quadrature.
210pub 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}