Repository Public
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