SPB Git

Repository Public

SpecialFunctions.swift 11.1 KB 257 lines swift

1import Foundation23/// Special functions behind the probability distributions. Accuracy targets ≈1e-13 relative4/// for moderate parameters (validated against SciPy in the test suite).5public enum SpecialFunctions {6    static let eps = 2.220446049250313e-167    static let tiny = 1e-30089    /// ln Γ(x) for x > 0.10    public static func logGamma(_ x: Double) -> Double {11        var sign: Int32 = 012        return lgamma_r(x, &sign)13    }1415    /// Remainder of Stirling's series: ln Γ(z) = (z − ½) ln z − z + ½ ln 2π + stirlingCorrection(z), for z ≥ 10.16    static func stirlingCorrection(_ z: Double) -> Double {17        let r = 1 / (z * z)18        return (1.0 / 12 - r * (1.0 / 360 - r * (1.0 / 1260 - r * (1.0 / 1680 - r * (1.0 / 1188 - r * (691.0 / 360360 - r / 156)))))) / z19    }2021    /// ln(1 + u) − u without cancellation for small |u|.22    static func log1pmx(_ u: Double) -> Double {23        if abs(u) > 0.3 { return log1p(u) - u }24        // −u²/2 + u³/3 − u⁴/4 + …25        var term = -u * u, sum = 0.026        var k = 2.027        while true {28            let add = term / k29            sum += add30            if abs(add) <= abs(sum) * 1e-17 || k > 200 { break }31            term *= -u32            k += 133        }34        return sum35    }3637    /// ln B(a, b). For large arguments the difference of log-gammas is formed analytically from38    /// Stirling's series, which avoids the cancellation of ln Γ(a) − ln Γ(a + b).39    public static func logBeta(_ a: Double, _ b: Double) -> Double {40        let hi = max(a, b), lo = min(a, b)41        guard hi >= 10 else { return logGamma(a) + logGamma(b) - logGamma(a + b) }42        // ln Γ(hi) − ln Γ(hi + lo)43        let diff = -(hi + lo - 0.5) * log1p(lo / hi) - lo * log(hi) + lo + stirlingCorrection(hi) - stirlingCorrection(hi + lo)44        return logGamma(lo) + diff45    }4647    /// ln of x^a e^{−x} / Γ(a), the prefactor of the incomplete gamma expansions.48    static func logGammaPrefix(_ a: Double, _ x: Double) -> Double {49        guard a >= 10 else { return -x + a * log(x) - logGamma(a) }50        // a·(ln(1+μ) − μ) + ½ ln(a / 2π) − corr(a), μ = (x − a)/a51        let mu = (x - a) / a52        let core = abs(mu) > 0.3 ? a * log(x / a) - (x - a) : a * log1pmx(mu)53        return core + 0.5 * log(a / (2 * Double.pi)) - stirlingCorrection(a)54    }5556    // MARK: Incomplete gamma5758    /// Regularised incomplete gamma functions (P, Q) with P + Q = 1, a > 0, x ≥ 0.59    /// Series for x < a + 1, modified-Lentz continued fraction otherwise; each tail is computed60    /// directly where it is small so neither loses relative accuracy.61    public static func gammaPQ(_ a: Double, _ x: Double) -> (p: Double, q: Double) {62        guard a > 0, x >= 0, !a.isNaN, !x.isNaN else { return (.nan, .nan) }63        if x == 0 { return (0, 1) }64        if x.isInfinite { return (1, 0) }65        let logPrefix = logGammaPrefix(a, x)66        let maxIter = 2000 + Int(20 * a.squareRoot())67        if x < a + 1 {68            var ap = a, del = 1 / a, sum = del69            for _ in 0..<maxIter {70                ap += 171                del *= x / ap72                sum += del73                if abs(del) < abs(sum) * eps { break }74            }75            let p = min(1, sum * exp(logPrefix))76            return (p, 1 - p)77        }78        var b = x + 1 - a79        var c = 1 / tiny80        var d = 1 / b81        var h = d82        for i in 1...maxIter {83            let an = -Double(i) * (Double(i) - a)84            b += 285            d = an * d + b86            if abs(d) < tiny { d = tiny }87            c = b + an / c88            if abs(c) < tiny { c = tiny }89            d = 1 / d90            let del = d * c91            h *= del92            if abs(del - 1) < eps { break }93        }94        let q = min(1, exp(logPrefix) * h)95        return (1 - q, q)96    }9798    /// Lower regularised incomplete gamma P(a, x).99    public static func gammaP(_ a: Double, _ x: Double) -> Double { gammaPQ(a, x).p }100    /// Upper regularised incomplete gamma Q(a, x).101    public static func gammaQ(_ a: Double, _ x: Double) -> Double { gammaPQ(a, x).q }102103    // MARK: Incomplete beta104105    private static func betaContinuedFraction(_ a: Double, _ b: Double, _ x: Double) -> Double {106        let qab = a + b, qap = a + 1, qam = a - 1107        var c = 1.0108        var d = 1 - qab * x / qap109        if abs(d) < tiny { d = tiny }110        d = 1 / d111        var h = d112        let maxIter = 3000 + Int(30 * max(a, b).squareRoot())113        for m in 1...maxIter {114            let dm = Double(m), m2 = 2 * dm115            var aa = dm * (b - dm) * x / ((qam + m2) * (a + m2))116            d = 1 + aa * d117            if abs(d) < tiny { d = tiny }118            c = 1 + aa / c119            if abs(c) < tiny { c = tiny }120            d = 1 / d121            h *= d * c122            aa = -(a + dm) * (qab + dm) * x / ((a + m2) * (qap + m2))123            d = 1 + aa * d124            if abs(d) < tiny { d = tiny }125            c = 1 + aa / c126            if abs(c) < tiny { c = tiny }127            d = 1 / d128            let del = d * c129            h *= del130            if abs(del - 1) < eps { break }131        }132        return h133    }134135    /// Regularised incomplete beta I_x(a, b) and its complement, given both x and y = 1 − x136    /// (pass y explicitly when it is known more accurately than 1 − x).137    public static func betaIPair(_ a: Double, _ b: Double, x: Double, y: Double) -> (p: Double, q: Double) {138        guard a > 0, b > 0, !x.isNaN, !y.isNaN else { return (.nan, .nan) }139        if x <= 0 { return (0, 1) }140        if y <= 0 { return (1, 0) }141        let logFront = a * (x > 0.5 ? log1p(-y) : log(x)) + b * (y > 0.5 ? log1p(-x) : log(y)) - logBeta(a, b)142        if x < (a + 1) / (a + b + 2) {143            let p = min(1, exp(logFront) * betaContinuedFraction(a, b, x) / a)144            return (p, 1 - p)145        }146        let q = min(1, exp(logFront) * betaContinuedFraction(b, a, y) / b)147        return (1 - q, q)148    }149150    /// Regularised incomplete beta I_x(a, b), 0 ≤ x ≤ 1.151    public static func betaI(_ a: Double, _ b: Double, _ x: Double) -> Double { betaIPair(a, b, x: x, y: 1 - x).p }152153    // MARK: Normal154155    /// Standard normal CDF Φ(x).156    public static func normalCDF(_ x: Double) -> Double { 0.5 * erfc(-x / 2.0.squareRoot()) }157158    /// Standard normal quantile Φ⁻¹(p): Acklam's rational approximation refined by one Halley step159    /// (full double precision). Use `normalQuantile(upper:)` for small upper-tail probabilities.160    public static func normalQuantile(_ p: Double) -> Double {161        guard p >= 0, p <= 1 else { return .nan }162        if p == 0 { return -.infinity }163        if p == 1 { return .infinity }164        if p > 0.5 { return -normalQuantileLower(1 - p) }   // 1 − p is exact for p ≥ 0.5165        return normalQuantileLower(p)166    }167168    /// Φ⁻¹(1 − q) computed from the upper-tail probability q without cancellation.169    public static func normalQuantile(upper q: Double) -> Double {170        guard q >= 0, q <= 1 else { return .nan }171        if q == 0 { return .infinity }172        if q == 1 { return -.infinity }173        if q > 0.5 { return normalQuantileLower(1 - q) }174        return -normalQuantileLower(q)175    }176177    /// Quantile for a lower-tail probability p ≤ 0.5.178    private static func normalQuantileLower(_ p: Double) -> Double {179        let a = [-3.969683028665376e+01, 2.209460984245205e+02, -2.759285104469687e+02, 1.383577518672690e+02, -3.066479806614716e+01, 2.506628277459239e+00]180        let b = [-5.447609879822406e+01, 1.615858368580409e+02, -1.556989798598866e+02, 6.680131188771972e+01, -1.328068155288572e+01]181        let c = [-7.784894002430293e-03, -3.223964580411365e-01, -2.400758277161838e+00, -2.549732539343734e+00, 4.374664141464968e+00, 2.938163982698783e+00]182        let d = [7.784695709041462e-03, 3.224671290700398e-01, 2.445134137142996e+00, 3.754408661907416e+00]183        var x: Double184        if p < 0.02425 {185            let q = (-2 * log(p)).squareRoot()186            x = (((((c[0] * q + c[1]) * q + c[2]) * q + c[3]) * q + c[4]) * q + c[5]) / ((((d[0] * q + d[1]) * q + d[2]) * q + d[3]) * q + 1)187        } else {188            let q = p - 0.5, r = q * q189            x = (((((a[0] * r + a[1]) * r + a[2]) * r + a[3]) * r + a[4]) * r + a[5]) * q / (((((b[0] * r + b[1]) * r + b[2]) * r + b[3]) * r + b[4]) * r + 1)190        }191        // Halley refinement on the lower tail (two steps: the second is a no-op at double precision in most of the range).192        for _ in 0..<2 {193            let err = 0.5 * erfc(-x / 2.0.squareRoot()) - p194            let dens = exp(-0.5 * x * x) / (2 * Double.pi).squareRoot()195            guard dens > 0 else { break }196            let step = err / dens197            x -= step / (1 + 0.5 * x * step)198        }199        return x200    }201202    // MARK: Generic monotone inversion203204    /// Solves F(x) = target for a continuous non-decreasing (increasing = true) or non-increasing function on205    /// (lo, hi) with a safeguarded Newton iteration (bisection whenever Newton leaves the bracket).206    /// `derivative` is |F′|. Infinite bounds are allowed; `guess` must be finite and inside the support.207    static func invertMonotone(target: Double, increasing: Bool, lo: Double, hi: Double, guess: Double,208                               f: (Double) -> Double, derivative: (Double) -> Double) -> Double {209        var a = lo, b = hi210        var x = guess211        if !(x > a && x < b) { x = a.isFinite && b.isFinite ? 0.5 * (a + b) : (a.isFinite ? a + 1 : (b.isFinite ? b - 1 : 0)) }212        func sign(_ fx: Double) -> Double { increasing ? fx - target : target - fx }213        // establish a finite bracket214        var step = max(1, abs(x))215        var guard1 = 0216        while a.isInfinite && guard1 < 2000 {217            let t = x - step218            if sign(f(t)) <= 0 { a = t } else { b = min(b, t); step *= 2 }219            guard1 += 1220        }221        step = max(1, abs(x)); guard1 = 0222        while b.isInfinite && guard1 < 2000 {223            let t = max(x, a) + step224            if sign(f(t)) >= 0 { b = t } else { a = max(a, t); step *= 2 }225            guard1 += 1226        }227        if !(x > a && x < b) { x = 0.5 * (a + b) }228        for _ in 0..<300 {229            let g = sign(f(x))230            if g == 0 { return x }231            if g < 0 { a = x } else { b = x }232            let d = derivative(x)233            let fx = increasing ? g + target : target - g234            var next = Double.nan235            if d > 0, d.isFinite {236                if fx > 0, target > 0 {237                    // Newton on ln F: converges quickly in the tails, where F is nearly exponential in x238                    let step = fx * log(fx / target) / d239                    next = increasing ? x - step : x + step240                } else {241                    next = x - g / d242                }243            }244            if !(next > a && next < b) {245                if a > 0 && b / a > 16 { next = (a * b).squareRoot() }      // geometric bisection across decades246                else if a == 0 && b > 0 && b < 1e-3 { next = b / 16 }247                else { next = 0.5 * (a + b) }248            }249            if next == x || abs(next - x) <= 2 * eps * abs(next) || (b - a) <= 4 * eps * max(abs(a), abs(b)) {250                return next251            }252            x = next253        }254        return x255    }256}257
Files main
Menu

Theme