Repository Public MIT
1<!--2ORIX Calc3File: docs/mathematics/numerical-methods.md4Author: Simon-Pierre Boucher5Contact: contact@spboucher.ai6-->7# Numerical methods89A reference of the numerical algorithms in ORIX Calc: what each one is, where it lives, the tolerances and limits that are10coded, and what happens when it fails. Paths are relative to `Packages/`. Tolerances are the defaults in the source;11callers that override them are listed in the last section. The representation of numbers is described in12[`docs/architecture/precision.md`](../architecture/precision.md).1314A rule shared by every entry: a failure is a typed error, a result kind (`.numerical`, `.unsupported`,15`.failedConvergence`) or a `VerificationReport` warning. No method returns NaN or a silent best guess as a result.1617## Shared kernels (`ORIXNumerics`)1819| Method | Algorithm | File | Tolerances and limits | Failure behaviour |20|---|---|---|---|---|21| `RootFinder.brent` | Brent's method (inverse quadratic interpolation, secant, bisection) on a bracketing interval | `ORIXNumerics/Sources/ORIXNumerics/RootFinding.swift` | `tolerance` 1e-14, stop when half-bracket ≤ `2·ulp·|b| + tolerance/2`; 200 iterations | `RootFindingError.notBracketed`, `.nonFiniteFunctionValue(at:)`, `.didNotConverge` |22| `RootFinder.allRoots` | Uniform scan for sign changes, each refined with Brent; a sign change across a pole is rejected by its residual; a local minimum of `|f|` without sign change is refined by golden section and accepted if it touches zero | same | 2000 sub-intervals, Brent tolerance 1e-13, `touchTolerance` 1e-9 (relative to neighbouring values); duplicates merged within `1e-9·max(1, |r|) + 1e-6·h` | Returns the roots found (possibly none); two roots inside one sub-interval can be merged or missed |23| `RootFinder.goldenMinimum` | Golden-section search on a unimodal function | same | relative tolerance 1e-12, at most 300 iterations | Returns the midpoint of the last bracket |24| `RootFinder.newton` | Newton iteration with central-difference derivative fallback (`h = 1e-6·max(|x|, 1)`) and step halving while `|f|` does not decrease | same | step tolerance 1e-13 relative, residual ≤ 1e-8; 100 iterations; up to 40 halvings per step | `.nonFiniteFunctionValue`, `.didNotConverge` |25| `Quadrature.integrate` | Globally adaptive Gauss–Kronrod (7, 15): the sub-interval with the largest error estimate is bisected | `ORIXNumerics/Sources/ORIXNumerics/Calculus.swift` | absolute 1e-12, relative 1e-10, 2000 subdivisions; infinite limits mapped by `x = t/(1 − t²)` | `converged == false` when the estimated error exceeds 10 × the tolerance or the value is not finite |26| `Quadrature.tanhSinh` | Tanh-sinh (double exponential) quadrature with step halving; tolerates integrable end-point singularities | same | relative 1e-12, 12 levels, abscissae up to `t = 6.5`; distance from each end point computed without cancellation | Divergence check: if terms with `t > 4.5` exceed 1e-9 of the sum, `converged == false` and the error estimate is `+∞` |27| `Differentiation.derivative` | Ridders' method (Neville extrapolation of central differences) | same | initial step `0.05·max(|x|, 1)`, shrink factor 1.4, tableau of 10; stops when the error grows by a factor 2 | `converged == false` when the error estimate exceeds `1e-6·max(1, |value|)` |28| `Differentiation.secondDerivative` | Ridders applied to the Ridders first derivative | same | inner step `1e-2·max(|x|, 1)` | as above |2930## Exact arithmetic and linear algebra (`ORIXExpression`)3132| Method | Algorithm | File | Tolerances and limits | Failure behaviour |33|---|---|---|---|---|34| Exact rationals | `BigRational`: numerator / denominator on `BigInt`, reduced by GCD; a finite `Double` is converted to its exact rational value | `ORIXExpression/Sources/ORIXExpression/BigRational.swift` | Non-integer rationals kept up to 8192 bits (`exactRationalBitLimit`); integers up to 4 000 000 bits (`exactIntegerBitLimit`) | Past the rational limit the calculation continues in double precision with a precision note; past the integer limit, an overflow error |35| Rational → `Double` | Scale so that the integer quotient has 64–66 significant bits, keep a sticky bit, round once (round-to-nearest-even); subnormal results are aligned to the subnormal grid first | same | Correctly rounded | ±infinity when out of range |36| Display digits | Decimal digits produced by exact rational arithmetic on the stored value, rounded half away from zero | `BigRational.swift`, `Formatter.swift` | The stored value is never modified | — |37| Factorial | Exact on `BigInt` | `ORIXExpression/Sources/ORIXExpression/Arithmetic.swift` | Up to 50000! | Overflow error beyond |38| Row reduction, determinant, rank, inverse, linear solve | Gauss–Jordan elimination. Exact entries stay exact (first non-zero pivot); inexact entries use partial pivoting | `ORIXExpression/Sources/ORIXExpression/LinearAlgebra.swift` | Zero threshold for inexact entries: `max(rows, cols) · scale · ulp · 4` | Inconsistent system → domain error. Verification: `‖A·A⁻¹ − I‖∞ < 1e-8` and `max|A·x − b|`, otherwise a warning |39| Eigenvalues | LAPACK `dgeev` (Accelerate); complex conjugate pairs returned as complex values | same | Verification: `|Σλ − tr(A)| ≤ 1e-9·scale·n` | Warning check when the trace test fails |40| `integral(expr, x, a, b)` | Gauss–Kronrod; if it does not converge on finite limits, tanh-sinh is tried and kept when it converges or has the smaller error | `ORIXExpression/Sources/ORIXExpression/Evaluator.swift` | Kernel defaults | `CalcError.nonConvergence` unless converged or error ≤ `1e-6·max(1, |value|)`; method, error estimate and evaluation count go to the verification report |41| `deriv(expr, x, a)` | Ridders | same | Kernel defaults | Domain error if not finite; warning when not converged |42| `nsolve(eq, x, …)` | Brent with two bounds, safeguarded Newton with one guess | same | Kernel defaults | `RootFindingError` messages; residual reported |43| Trigonometry at special angles | Exact table; snapping of the double nearest to `k·π/2` | `ORIXExpression/Sources/ORIXExpression/Trigonometry.swift` | — | Poles (`tan 90°`) are domain errors |4445Inside a compiled (plotted) function, `integral` runs with absolute 1e-10, relative 1e-9 and 200 subdivisions, `deriv`46with the kernel defaults, and `nsolve` is rejected (`Compile.swift`).4748## Financial (`ORIXFinancial`)4950| Method | Algorithm | File | Tolerances and limits | Failure behaviour |51|---|---|---|---|---|52| TVM closed forms | `log1p` / `expm1` forms of the discount and annuity factors; zero rate exact | `ORIXFinancial/Sources/ORIXFinancial/TVM.swift` | — | `.noSolution`, `.nonConvergence` on overflow |53| TVM rate (I/Y) | `allRoots` on an overflow-free form of the equation in `x = ln(1 + i)` | same | `x ∈ [ln 1e-4, ln 1e3]`, 6000 intervals, Brent tolerance 1e-15 | `.noSolution` (same signs or no root), `.multipleSolutions(candidates:)` |54| NPV / NFV | Horner's rule in the stable direction (`1/(1+r)` for `r ≥ 0`, `1 + r` for `r < 0`) | `ORIXFinancial/Sources/ORIXFinancial/CashFlows.swift` | 20 000 periods | `.invalidInput`, `.nonConvergence` on overflow |55| IRR | Descartes sign count; one sign change → direct Brent bracket; otherwise `allRoots` on both unit intervals | same | lower end 1e-6, 4000 intervals, Brent tolerance 1e-16; duplicates merged within 1e-9 | `IRROutcome.none(reason:)` or `.multiple` — results, not errors |56| Money-weighted return | `allRoots` in `u = ln(1 + r)`, Actual/365 | `ORIXFinancial/Sources/ORIXFinancial/Investment.swift` | `u ∈ [ln 1e-6, ln 1e6]`, 6000 intervals, tolerance 1e-15 | `IRROutcome` as above |57| Amortization schedule | Period-by-period loop; cent rounding in Foundation `Decimal`, half away from zero | `ORIXFinancial/Sources/ORIXFinancial/Loans.swift` | 20 000 payments | `.invalidInput` when a payment does not cover the interest; `.nonConvergence` at the limit |58| Bond yield | Bracket by halving `1 + y/f` and doubling the yield, then Brent | `ORIXFinancial/Sources/ORIXFinancial/Bonds.swift` | tolerance 1e-15, 200 iterations (parameter); `1 + y/f ≥ 1e-9`, yield ≤ 1e6 | `.noSolution` (price too high / too low), `.nonConvergence` |59| Duration and convexity cross-checks | Analytic sums compared with Ridders first and second derivatives of the price | same | relative gaps 1e-6 and 1e-4 | Failed verification check |60| Normal CDF | `½·erfc(−x/√2)` | `ORIXFinancial/Sources/ORIXFinancial/Options.swift` | libm | — |61| Implied volatility | No-arbitrage bounds, bracket from 1e-6 with the upper end doubling from 1 to 64, then Brent | same | tolerance 1e-15, 200 iterations (parameter) | `.outsideNoArbitrageBounds`, `.nonConvergence` |62| Binomial tree | Cox–Ross–Rubinstein backward induction in a single array | same | 1 to 10 000 steps | `.invalidInput` when the risk-neutral probability leaves (0, 1) |6364## Statistics (`ORIXStatistics`)6566| Method | Algorithm | File | Tolerances and limits | Failure behaviour |67|---|---|---|---|---|68| `logGamma`, `gamma`, `erf`, `erfc` | libm (`lgamma_r`, `tgamma`, `erf`, `erfc`) | `ORIXStatistics/Sources/ORIXStatistics/SpecialFunctions.swift` | `gamma` overflows above about 171.62 | `StatisticsError` at poles and on overflow |69| `logBeta`, prefactors | Stirling remainder and `log1p(u) − u`, so that large shapes do not cancel | same | — | Domain errors |70| Regularized incomplete gamma P, Q | Power series for small arguments (with a dedicated assembly of Q for `a < 1`, `x < 1`), continued fraction by modified Lentz otherwise; the smaller of P and Q is computed directly | same | term test at machine epsilon; iteration cap `2000 + 60·√max(a, x)` | `StatisticsError.nonConvergence` |71| Regularized incomplete beta | Continued fraction (even contraction of DiDonato & Morris / Boost) by modified Lentz | same | iteration cap `1000 + 60·√max(a, b)` | `StatisticsError.nonConvergence` |72| Inverse incomplete gamma / beta | Safeguarded Newton on the logarithm of the smaller tail inside a bracket; Brent fallback | same | 120 Newton iterations; Brent with tolerance 0 and 400 iterations | `StatisticsError.nonConvergence`; domain errors for probabilities that map to ±∞ |73| Inverse error function | Maclaurin start, then Halley iterations on `erf(x) − y` | same | — | ±1 throw |74| Normal quantile | Acklam's rational approximation (relative error below 1.15e-9) polished by two Halley steps on `½·erfc`; asymptotic Mills ratio where the density underflows | same | — | 0 and 1 throw |75| Student t with large ν | Hill's (1970) expansion, Algorithm 395 | `ORIXStatistics/Sources/ORIXStatistics/Distributions.swift` | above ν = 1e5 (`hillThreshold`) | — |76| Discrete quantiles | Smallest `k` with `cdf(k) ≥ p`, compared against `p·(1 − 64ε)` | `ORIXStatistics/Sources/ORIXStatistics/DiscreteDistributions.swift` | — | Parameter and probability errors |77| Summation | Neumaier compensated sum; central moments about the compensated mean | `ORIXStatistics/Sources/ORIXStatistics/Descriptive.swift` | — | Errors for empty input, NaN, `n` too small |78| Sample quantiles | Nine definitions; default R-7 (`.linear`) | same | — | as above |79| Least squares | Householder QR with column pivoting (Businger & Golub) on the column-equilibrated design matrix; never forms `XᵀX` | `ORIXStatistics/Sources/ORIXStatistics/LinearAlgebra.swift` | `rankTolerance` 1e-10 relative to the largest pivot | Rank deficiency reported with an explanatory message |80| Curve fits | Exponential and power models by linearising transformation; polynomial fits on raw powers | `ORIXStatistics/Sources/ORIXStatistics/Regression.swift` | — | Verification warning from degree 4 upwards |81| Random generator | xoshiro256** seeded by four SplitMix64 outputs; stream `k` seeds with `seed ^ SplitMix64(k)` | `ORIXStatistics/Sources/ORIXStatistics/Random.swift` | 256 bits of state; not cryptographic | — |82| Uniform variates | `(next() >> 11)·2⁻⁵³` on [0, 1); `((next() >> 11) + ½)·2⁻⁵³` on (0, 1); unbiased integers by Lemire's multiply-and-reject | same | — | — |83| Normal, exponential | Marsaglia's polar method (second value discarded); inversion `−ln U` | same | — | — |84| Gamma, beta | Marsaglia & Tsang (2000); shape < 1 through `Gamma(shape + 1)·U^(1/shape)`; beta as `X/(X + Y)` in logarithms | same | — | — |85| Binomial | Recursive halving through a beta-distributed order statistic, sequential CDF inversion once `n ≤ 32` | same | exact (no normal approximation) | — |86| Poisson | CDF inversion for `λ < 30`; Ahrens & Dieter's (1974) gamma method otherwise | same | exact | — |87| Geometric, negative binomial | Inversion `⌊ln U / ln(1 − p)⌋`; gamma–Poisson mixture | same | — | — |88| Shuffle, resampling | Fisher–Yates with `uniformInteger` | same | — | — |89| Bootstrap intervals | Percentile, basic and BCa (bias correction with ties counted half, acceleration from the jackknife) | `ORIXStatistics/Sources/ORIXStatistics/Simulation.swift` | 2000 resamples by default | Explicit error when BCa is undefined |9091## Symbolic and numerical mathematics (`ORIXSymbolic`)9293| Method | Algorithm | File | Tolerances and limits | Failure behaviour |94|---|---|---|---|---|95| Polynomial arithmetic | Exact rational coefficients: division with remainder, primitive GCD, Horner evaluation, composition | `ORIXSymbolic/Sources/ORIXSymbolic/Polynomial.swift` | degree 400 | `.unsupported` beyond |96| Factorisation over ℚ | Content, square-free decomposition, rational roots, Kronecker's method for factors of degree 2–4 | `ORIXSymbolic/Sources/ORIXSymbolic/Factor.swift` | bounded number of Kronecker candidates | Remaining factor flagged `isProvenIrreducible == false` |97| Polynomial roots | Exact for linear, quadratic and biquadratic factors; otherwise Durand–Kerner simultaneous iteration followed by Newton polishing | same | 2000 iterations, change ≤ `1e-15·radius`; 8 polishing steps; imaginary parts below 1e-11 relative snapped to 0 | `nil` when not converged; roots labelled `.numerical` with a residual check |98| Equation solving, numerical fallback | `RootFinder.allRoots` on the interval | `ORIXSymbolic/Sources/ORIXSymbolic/Solve.swift` | 4000 intervals; default interval [−10, 10]; residual tolerance 1e-8 (1e-6 for multiple or numerical roots) relative to the scale | Roots that fail substitution are rejected and listed |99| Linear systems | Exact rational Gaussian elimination | `ORIXSymbolic/Sources/ORIXSymbolic/Systems.swift` | 60 equations × 60 unknowns | Inconsistent / underdetermined reported; `fail` beyond the limit |100| Nonlinear systems | Newton's method with a central-difference Jacobian (`h = 1e-6·max(1, |x|)`) and step halving, from the given guesses plus 80 (n ≤ 2) or 160 deterministic pseudo-random starts | same | accept `‖F‖ ≤ 1e-13`, or ≤ 1e-9 when the step stalls or after 80 iterations; solutions merged within 1e-7 | No solution found is reported; results are numerical |101| Definite integrals | Verified antiderivative when the integrand is continuous; otherwise Gauss–Kronrod with tanh-sinh fallback. Poles are searched with `allRoots` on `1/f` | `ORIXSymbolic/Sources/ORIXSymbolic/Definite.swift` | 1500 samples for the pole search | Result labelled `.numerical`; exact value discarded when quadrature disagrees |102| Derivative verification | Symbolic derivative compared with Ridders | `ORIXSymbolic/Sources/ORIXSymbolic/Differentiate.swift` | step `1e-3·max(1, |x₀|)` | Verification check |103| Numerical limits | Richardson-style extrapolation (Neville's algorithm on a geometric sequence of steps) from each side | `ORIXSymbolic/Sources/ORIXSymbolic/Limits.swift` | accepted when the error ≤ `1e-6·max(1, |value|)`; sides agree within 1e-7 | `.numerical` with an error estimate, or `.failedConvergence` |104| 1-D optimisation | Critical points from `allRoots` on `f′` (3000 intervals), classified with `f″` and, failing that, the sign change of `f′` | `ORIXSymbolic/Sources/ORIXSymbolic/Optimize.swift` | `|f′| ≤ 1e-6` at critical points | Warning check |105| Multivariate minimisation | Nelder–Mead from the start point, then BFGS polishing with the symbolic gradient and a step-halving line search | same | Nelder–Mead: `4000·n` iterations, value spread ≤ 1e-14 and simplex size ≤ 1e-9 (relative); BFGS stops at gradient norm ≤ 1e-11 (relative); stationary when norm ≤ 1e-6 | One local minimum, labelled numerical; gradient norm reported |106| ODE, fixed step | Classical fourth-order Runge–Kutta | `ORIXSymbolic/Sources/ORIXSymbolic/ODE.swift` | Verification by recomputing with twice the steps (Richardson factor 16/15) | Warning when the refinement gap exceeds 1e-4 |107| ODE, adaptive | Dormand–Prince 5(4) with embedded error estimate; step factor `0.9·err^(−0.2)` clamped to [0.2, 5] | same | default `rtol` 1e-8, `atol` 1e-10 (`rtol ≥ 1e-14`); 200 000 steps; verification by recomputing with tolerances ÷ 10 | `.failedConvergence` on step-size underflow, blow-up or the step limit (message suggests stiffness) |108109## Graphing (`ORIXGraph`)110111| Method | Algorithm | File | Tolerances and limits | Failure behaviour |112|---|---|---|---|---|113| Explicit sampling | One sample per pixel column, varying interior test point, bisection on screen deviation, aliasing probes, bisection of gaps to adjacent doubles with one-sided limit estimation, golden-section search for even poles | `ORIXGraph/Sources/ORIXGraph/Sampler.swift` | 0.2 px tolerance, depth 6, clipping at ± one viewport height | Bands and discontinuity records instead of a line; `.incomplete` notice on cancellation or budget exhaustion |114| Parametric / polar sampling | Adaptive refinement by screen-space deviation | `ORIXGraph/Sources/ORIXGraph/CurveSampler.swift` | 512 initial samples, depth 10 | Broken at undefined values and jumps |115| Implicit curves, regions, contours | Adaptive marching squares with validated crossings | `ORIXGraph/Sources/ORIXGraph/ImplicitPlotter.swift`, `Surface.swift` | 8 px coarse lattice, 2 px cells; crossing thresholds 2 % and 16-fold bracket shrink | `reliable == false` with reasons |116| Surface mesh | Grid mesh, Tukey-fence z-range, triangles dropped across undefined points and discontinuities | `ORIXGraph/Sources/ORIXGraph/Surface.swift` | 5 % of the z-range edge test | `droppedTriangles`, notices |117| Depth ordering | Painter's algorithm on triangle centroids | `ORIXGraph/Sources/ORIXGraph/Camera3D.swift` | — | Not guaranteed for self-overlapping parametric surfaces |118| Roots, extrema, intersections, inflections | `allRoots`, golden section, Brent on the Ridders derivative | `ORIXGraph/Sources/ORIXGraph/Analysis.swift` | 2000 samples (800 for inflections) | Poles and jumps excluded |119| Integral, area, arc length | Pole scan at 2048 columns, then Gauss–Kronrod between jumps or tanh-sinh for end-point singularities | same | Kernel defaults | `GraphError.refused(message)` when a pole or undefined stretch is inside |120| Fit overlay | Least-squares line | `ORIXGraph/Sources/ORIXGraph/Data.swift` | — | `nil` when undefined |121122## Units (`ORIXUnits`)123124| Method | Algorithm | File | Tolerances and limits | Failure behaviour |125|---|---|---|---|---|126| Conversion | Exact fraction of big integers, divided once by schoolbook long division | `ORIXUnits/Sources/ORIXUnits/ExactArithmetic.swift`, `UnitConverter.swift` | Exact when the result terminates within 38 significant digits, otherwise rounded half-to-even to 38 digits; exponents 10⁻¹²⁸ … 10¹²⁷ | `UnitError.notRepresentable` |127| `Double` path | Shortest round-trip string → `Decimal` → nearest double | `ORIXUnits/Sources/ORIXUnits/UnitConverter.swift` | Outside 1e-60 … 1e60, binary arithmetic with a few ulps of error | — |128| Rate conventions | Conversion through the effective annual rate with `log1p` / `expm1` | `ORIXUnits/Sources/ORIXUnits/RateConvention.swift` | `Double` only | — |129130## Where the defaults are overridden131132| Caller | Kernel | Override |133|---|---|---|134| `TVM.solveRate` | `allRoots` | 6000 samples, tolerance 1e-15 |135| `CashFlowSeries.irr` | `brent`, `allRoots` | tolerance 1e-16, 4000 samples |136| `Returns.moneyWeighted` | `allRoots` | 6000 samples, tolerance 1e-15 |137| `Bond.solveYield`, `BlackScholes.impliedVolatility` | `brent` | tolerance 1e-15, `maxIterations` parameter |138| Inverse incomplete gamma / beta | `brent` | tolerance 0, 400 iterations |139| `CompiledExpression` (`integral`) | `Quadrature.integrate` | absolute 1e-10, relative 1e-9, 200 subdivisions |140| `Solve` numerical fallback | `allRoots` | 4000 samples |141| `Optimize` (1-D) | `allRoots` | 3000 samples |142| `Definite` pole search | `allRoots` | 1500 samples |143| `GraphAnalysis.extrema` | `brent` | tolerance 1e-15 |144