dymokomi/luce-std
Source of release 0.7.4
#==============================================================================================
#
# exp - The exponential functions: exp, exp2, expm1, and e^x as a pair for the others
#
# DESCRIPTION:
# exp and exp2 with normal results first try the fast path at the end of this file,
# which returns only results it proves correctly rounded. The method is Tang's table-driven exponential, as ARM's optimized-routines and musl
# compute exp: x = (128m + j)·ln2/128 + r with |r| <= ln2/256, so
# e^x = 2^m · 2^(j/128) · e^r. The table holds 2^(j/128) as a double and its remainder;
# e^r - 1 is its Taylor polynomial to r^6, whose truncation stays below 2^-71. Written
# anew from the method; the tables come from tools/math_tables.py. A result is within
# 0.51 ulp; `exp_pair` keeps about 2^-68 for pow and the hyperbolic functions.
#
#==============================================================================================
## 1.5·2^52: adding and subtracting it rounds a double below 2^51 to an integer, in the
## default rounding direction.
let round_shift: f64 = 6755399441055744.0
## 2^m for an integer m in [-1022, 1023], built from its bits.
inline func power_of_two(m: i64) -> f64:
return f64.bits((u64)(m + 1023) << 52)
## The reduction of `xh + xl` (|xh| < 746): `k` with `x = k·ln2/128 + r`, and `r` as a pair.
## `k·ln2_128_high` is exact (35 bits times 18), and so is `xh` less it.
inline func exp_reduce(xh: f64, xl: f64) -> (i64, f64, f64):
let kd = (xh * f64.bits(inverse_ln2_128) + round_shift) - round_shift
let r1 = xh - kd * f64.bits(ln2_128_high)
let (rh, rl) = two_sum(r1, -(kd * f64.bits(ln2_128_low)))
return ((i64)kd, rh, rl + xl)
## e^r's Taylor coefficients from r²: 1/2!, ..., 1/6!.
let exp_coefficients: f64[5] = [0.5, 0.16666666666666666, 0.041666666666666664, 0.008333333333333333, 0.001388888888888889]
## e^r - 1 less r, for |r| <= ln2/256 + 2^-40: r²(1/2 + r/6 + ... + r^4/720).
inline func exp_polynomial(r: f64) -> f64:
let k = exp_coefficients
return r * r * (k[0] + r * (k[1] + r * (k[2] + r * (k[3] + r * k[4]))))
## `(vh + vl)·2^m` rounded once, for `vh` in [0.5, 4): exact scaling while the result is
## normal, infinity past the largest double, and below the normal range the pair is
## rounded to the subnormal grid in one step (adding 1 places the grid at 2^-52).
func scale_pair(vh: f64, vl: f64, m: i64) -> f64:
if m >= -1020 and m <= 1023:
return (vh + vl) * power_of_two(m)
if m > 1023:
if m > 1024:
return f64.bits(0x7ff0000000000000)
return ((vh + vl) * power_of_two(m - 1)) * 2.0
if m < -1080:
return 0.0
let s = power_of_two(m + 1022)
let wh = vh * s
let wl = vl * s
if wh > 1.0 or (wh == 1.0 and wl >= 0.0):
return (wh + wl) * power_of_two(-1022)
let (a, ae) = two_sum(1.0, wh)
let b = a + (ae + wl)
return (b - 1.0) * power_of_two(-1022)
## e^x as `(vh, vl, m)`, the value `(vh + vl)·2^m` with `vh` in [0.99, 2.01), to about
## 2^-68 relative: the table pair times `1 + p` with the product's error kept.
inline func exp_pair(xh: f64, xl: f64) -> (f64, f64, i64):
let (k, rh, rl) = exp_reduce(xh, xl)
let j = (usize)(k & 127)
let th = f64.bits(exp_table_high[j])
let tl = f64.bits(exp_table_low[j])
let (ph, pl) = fast_two_sum(rh, rl + rh * rl + exp_polynomial(rh))
let (a, ae) = two_product(th, ph)
let (vh, vl) = fast_two_sum(th, a)
return (vh, vl + (ae + (th * pl + tl * (1.0 + ph))), k >> 7)
## e^x, within 0.51 ulp: one table product and one rounding, then `scale_pair`.
func exp_accurate(x: f64) -> f64:
if not (x < 709.8):
return x + x if x != x else f64.bits(0x7ff0000000000000)
if x < -746.0:
return 0.0
let (k, rh, rl) = exp_reduce(x, 0.0)
let j = (usize)(k & 127)
let th = f64.bits(exp_table_high[j])
let p = rh + (rl + exp_polynomial(rh))
return scale_pair(th, f64.bits(exp_table_low[j]) + th * p, k >> 7)
## 2^x: x splits exactly into k/128 + r, and e^(r·ln2) is exp's polynomial.
func exp2_accurate(x: f64) -> f64:
if not (x < 1024.0):
return x + x if x != x else f64.bits(0x7ff0000000000000)
if x < -1080.0:
return 0.0
let kd = (x * 128.0 + round_shift) - round_shift
let k = (i64)kd
let (rh, rl) = multiply_pair(f64.bits(ln2_double_high), f64.bits(ln2_double_low), x - kd * 0.0078125)
let j = (usize)(k & 127)
let th = f64.bits(exp_table_high[j])
let p = rh + (rl + exp_polynomial(rh))
return scale_pair(th, f64.bits(exp_table_low[j]) + th * p, k >> 7)
## e^x - 1. Near zero (k = 0) it is the polynomial itself, with nothing cancelled;
## elsewhere it is the exp pair, scaled, less one.
func expm1_value(x: f64) -> f64:
if not (x < 709.8):
return x + x if x != x else f64.bits(0x7ff0000000000000)
if x < -40.0:
return -1.0
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude < 0x3c90000000000000:
# below 2^-54, x²/2 is under half an ulp of x: x itself, signed zero kept
return x
if x > 40.0:
return exp_value(x)
let (k, rh, rl) = exp_reduce(x, 0.0)
if k == 0:
return rh + (rl + rh * rl + exp_polynomial(rh))
let (vh, vl, m) = exp_pair(x, 0.0)
let s = power_of_two(m)
let (d, de) = two_sum(vh * s, -1.0)
return d + (de + vl * s)
# mark: The fast path =========================================================================
# For results in the normal range, exp and exp2 first try the same table with more of
# the work exact: r = rh + rl with the subtraction's error kept (two_sum, and the product
# k·ln2_128_low's by a fused multiply-add), 2^(j/128)·rh exact as a pair, and
# 2^(j/128) + that an exact sum. What is left, the table's low part and
# 2^(j/128)·(rl + rh²·P(rh)) for P e^r's Taylor series from 1/2 to 1/720, is under 2^-17
# of the result and summed in doubles.
#
# The error budget, relative to the result's 2^(j/128)·e^r in [1, 2): P's truncation
# (r^7/5040) 2^-72; P's evaluation and the square 2^-71; the dropped rh·rl and
# Tl·(rl + rh²·P) 2^-70; four roundings of terms under 2^-17, 2^-69; the reduction's
# ln2_128_low and the table's low parts 2^-86. The total is under 2^-67; the test allows
# 2^-63, so when h + (l - 2^-63) and h + (l + 2^-63) round alike, the exact value rounds to
# them too, and the scaling by 2^m is exact: the result is correctly rounded. The rest,
# about one input in a thousand, go to exp_accurate.
## e^r - 1 - r for |r| <= ln2/256 + 2^-40, less nothing below 2^-72: r²·P(r).
inline func exp_series(r: f64) -> f64:
let r2 = r * r
let low = r.mul_add(0.16666666666666666, 0.5)
let middle = r.mul_add(0.008333333333333333, 0.041666666666666664)
let high = r.mul_add(0.0001984126984126984, 0.001388888888888889)
return r2 * r2.mul_add(r2.mul_add(high, middle), low)
## 2^(k/128)·e^(rh + rl) / 2^(k >> 7) as a double h in [1, 2] and a remainder l.
inline func exp_table_pair(k: i64, rh: f64, rl: f64) -> (f64, f64):
let j = (usize)(k & 127)
let th = f64.bits(exp_table_high[j])
let tl = f64.bits(exp_table_low[j])
let (ph, pl) = two_product(th, rh)
let (h, he) = fast_two_sum(th, ph)
return (h, (he + pl) + (tl + (th * (rl + exp_series(rh)) + tl * rh)))
## Whether h + l, h in [1, 2], rounds the same at both ends of 2^-63.
inline func exp_rounds_alike(h: f64, l: f64) -> bool:
return h + (l - 1.0842021724855044e-19) == h + (l + 1.0842021724855044e-19)
## Whether e^x is normal, where the fast path takes x: -708 < x < 709.7.
inline func exp_inside(x: f64) -> bool:
return x > -708.0 and x < 709.7
## e^x by the fast path as (h + l)·2^m, h + l in [1, 2]; any x below 2^62 in magnitude
## runs through it without a trap, m then being garbage.
inline func exp_parts(x: f64) -> (f64, f64, i64):
let kd = (x * f64.bits(inverse_ln2_128) + round_shift) - round_shift
let p = kd * f64.bits(ln2_128_low)
let (rh, re) = two_sum(x - kd * f64.bits(ln2_128_high), -p)
let k = (i64)kd
let (h, l) = exp_table_pair(k, rh, re - kd.mul_add(f64.bits(ln2_128_low), -p))
return (h, l, k >> 7)
## e^x: the fast path where it vouches for its rounding, else exp_accurate.
func exp_value(x: f64) -> f64:
if exp_inside(x):
let (h, l, m) = exp_parts(x)
if exp_rounds_alike(h, l):
return (h + l) * power_of_two(m)
return exp_accurate(x)
## 2^x: x = k/128 + r exactly, and r·ln2 as a pair, for -1022 < x < 1024.
func exp2_value(x: f64) -> f64:
if x > -1022.0 and x < 1024.0:
let kd = (x * 128.0 + round_shift) - round_shift
let r = x - kd * 0.0078125
let rh = r * f64.bits(ln2_double_high)
let rl = r.mul_add(f64.bits(ln2_double_high), -rh) + r * f64.bits(ln2_double_low)
let k = (i64)kd
let (h, l) = exp_table_pair(k, rh, rl)
if exp_rounds_alike(h, l):
return (h + l) * power_of_two(k >> 7)
return exp2_accurate(x)