SPB Git

Repository Public MIT

numerical-methods.md 20.3 KB

# Numerical methods

A reference of the numerical algorithms in ORIX Calc: what each one is, where it lives, the tolerances and limits that are coded, and what happens when it fails. Paths are relative to Packages/. Tolerances are the defaults in the source; callers that override them are listed in the last section. The representation of numbers is described in docs/architecture/precision.md.

A rule shared by every entry: a failure is a typed error, a result kind (.numerical, .unsupported, .failedConvergence) or a VerificationReport warning. No method returns NaN or a silent best guess as a result.

# Shared kernels (ORIXNumerics)

Method Algorithm File Tolerances and limits Failure behaviour
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
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
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
RootFinder.newton Newton iteration with central-difference derivative fallback (`h = 1e-6·max( x , 1)) and step halving while f
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
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 +∞
Differentiation.derivative Ridders' method (Neville extrapolation of central differences) same initial step `0.05·max( x
Differentiation.secondDerivative Ridders applied to the Ridders first derivative same inner step `1e-2·max( x

# Exact arithmetic and linear algebra (ORIXExpression)

Method Algorithm File Tolerances and limits Failure behaviour
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
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
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 —
Factorial Exact on BigInt ORIXExpression/Sources/ORIXExpression/Arithmetic.swift Up to 50000! Overflow error beyond
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
Eigenvalues LAPACK dgeev (Accelerate); complex conjugate pairs returned as complex values same Verification: ` Σλ − tr(A)
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,
deriv(expr, x, a) Ridders same Kernel defaults Domain error if not finite; warning when not converged
nsolve(eq, x, …) Brent with two bounds, safeguarded Newton with one guess same Kernel defaults RootFindingError messages; residual reported
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

Inside a compiled (plotted) function, integral runs with absolute 1e-10, relative 1e-9 and 200 subdivisions, deriv with the kernel defaults, and nsolve is rejected (Compile.swift).

# Financial (ORIXFinancial)

Method Algorithm File Tolerances and limits Failure behaviour
TVM closed forms log1p / expm1 forms of the discount and annuity factors; zero rate exact ORIXFinancial/Sources/ORIXFinancial/TVM.swift — .noSolution, .nonConvergence on overflow
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:)
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
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
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
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
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
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
Normal CDF ½·erfc(−x/√2) ORIXFinancial/Sources/ORIXFinancial/Options.swift libm —
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
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)

# Statistics (ORIXStatistics)

Method Algorithm File Tolerances and limits Failure behaviour
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
logBeta, prefactors Stirling remainder and log1p(u) − u, so that large shapes do not cancel same — Domain errors
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
Regularized incomplete beta Continued fraction (even contraction of DiDonato & Morris / Boost) by modified Lentz same iteration cap 1000 + 60·√max(a, b) StatisticsError.nonConvergence
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 ±∞
Inverse error function Maclaurin start, then Halley iterations on erf(x) − y same — ±1 throw
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
Student t with large ν Hill's (1970) expansion, Algorithm 395 ORIXStatistics/Sources/ORIXStatistics/Distributions.swift above ν = 1e5 (hillThreshold) —
Discrete quantiles Smallest k with cdf(k) ≥ p, compared against p·(1 − 64ε) ORIXStatistics/Sources/ORIXStatistics/DiscreteDistributions.swift — Parameter and probability errors
Summation Neumaier compensated sum; central moments about the compensated mean ORIXStatistics/Sources/ORIXStatistics/Descriptive.swift — Errors for empty input, NaN, n too small
Sample quantiles Nine definitions; default R-7 (.linear) same — as above
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
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
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 —
Uniform variates (next() >> 11)·2⁻⁵³ on [0, 1); ((next() >> 11) + ½)·2⁻⁵³ on (0, 1); unbiased integers by Lemire's multiply-and-reject same — —
Normal, exponential Marsaglia's polar method (second value discarded); inversion −ln U same — —
Gamma, beta Marsaglia & Tsang (2000); shape < 1 through Gamma(shape + 1)·U^(1/shape); beta as X/(X + Y) in logarithms same — —
Binomial Recursive halving through a beta-distributed order statistic, sequential CDF inversion once n ≤ 32 same exact (no normal approximation) —
Poisson CDF inversion for λ < 30; Ahrens & Dieter's (1974) gamma method otherwise same exact —
Geometric, negative binomial Inversion ⌊ln U / ln(1 − p)⌋; gamma–Poisson mixture same — —
Shuffle, resampling Fisher–Yates with uniformInteger same — —
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

# Symbolic and numerical mathematics (ORIXSymbolic)

Method Algorithm File Tolerances and limits Failure behaviour
Polynomial arithmetic Exact rational coefficients: division with remainder, primitive GCD, Horner evaluation, composition ORIXSymbolic/Sources/ORIXSymbolic/Polynomial.swift degree 400 .unsupported beyond
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
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
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
Linear systems Exact rational Gaussian elimination ORIXSymbolic/Sources/ORIXSymbolic/Systems.swift 60 equations × 60 unknowns Inconsistent / underdetermined reported; fail beyond the limit
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
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
Derivative verification Symbolic derivative compared with Ridders ORIXSymbolic/Sources/ORIXSymbolic/Differentiate.swift step `1e-3·max(1, x₀
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
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′
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
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
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)

# Graphing (ORIXGraph)

Method Algorithm File Tolerances and limits Failure behaviour
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
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
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
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
Depth ordering Painter's algorithm on triangle centroids ORIXGraph/Sources/ORIXGraph/Camera3D.swift — Not guaranteed for self-overlapping parametric surfaces
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
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
Fit overlay Least-squares line ORIXGraph/Sources/ORIXGraph/Data.swift — nil when undefined

# Units (ORIXUnits)

Method Algorithm File Tolerances and limits Failure behaviour
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
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 —
Rate conventions Conversion through the effective annual rate with log1p / expm1 ORIXUnits/Sources/ORIXUnits/RateConvention.swift Double only —

# Where the defaults are overridden

Caller Kernel Override
TVM.solveRate allRoots 6000 samples, tolerance 1e-15
CashFlowSeries.irr brent, allRoots tolerance 1e-16, 4000 samples
Returns.moneyWeighted allRoots 6000 samples, tolerance 1e-15
Bond.solveYield, BlackScholes.impliedVolatility brent tolerance 1e-15, maxIterations parameter
Inverse incomplete gamma / beta brent tolerance 0, 400 iterations
CompiledExpression (integral) Quadrature.integrate absolute 1e-10, relative 1e-9, 200 subdivisions
Solve numerical fallback allRoots 4000 samples
Optimize (1-D) allRoots 3000 samples
Definite pole search allRoots 1500 samples
GraphAnalysis.extrema brent tolerance 1e-15
Files main
Menu

Theme