dymokomi/luce-std
Source of release 0.7.5
0.7.5 / src / math / inverse.lucb
#==============================================================================================
#
# inverse - The inverse trigonometric functions: atan, atan2, asin and acos
#
# DESCRIPTION:
# atan and atan2 of arguments between 2^-500 and 2^500 first try the fast path at the
# end of this file, which returns only results it proves correctly rounded. atan follows the table-driven method of Gal's accurate tables (as in IBM's
# libultim, which glibc used): for t in [0, 1], c = j/64 is the nearest point and
# atan t = atan c + atan v with v = (t - c)/(1 + t·c), |v| <= 2^-7, whose series to
# v^9 stays below 2^-70 of v. t above 1 uses pi/2 - atan(1/t). For t = y/x, v is
# (y - c·x)/(x + c·y), one quotient taken as a pair, so atan2 loses nothing to y/x's
# rounding. asin follows fdlibm: up to 1/2, x + x³·P(x²), P here a Chebyshev fit made
# by tools/math_tables.py; beyond, pi/2 - 2·asin(sqrt((1 - x)/2)), the root a pair.
# acos is pi/2 less asin, or twice that asin. The special cases are C99 Annex F.9.1's.
# Written anew from the methods; the tables come from tools/math_tables.py.
#
#==============================================================================================
## atan(y/x) as a pair, for 0 <= y <= x: c = j/64 nearest y/x, and
## v = (y - c·x)/(x + c·y), which is (t - c)/(1 + t·c) for t = y/x with one division.
## y - c·x is exact, c being within a factor two of y/x or zero.
inline func atan_ratio(y: f64, x: f64) -> (f64, f64):
let jd = (y / x * 64.0 + round_shift) - round_shift
let j = (usize)(i64)jd
let c = jd * 0.015625
let (p, pe) = two_product(c, x)
let (nh, nl) = two_sum(y - p, -pe)
let (q, qe) = two_product(c, y)
let (dh, de) = fast_two_sum(x, q)
let (vh, vl) = divide_pairs(nh, nl, dh, de + qe)
let z = vh * vh
let k = atan_coefficients
let series = vh * z * (k[0] + z * (k[1] + z * (k[2] + z * k[3])))
let (s, se) = fast_two_sum(f64.bits(atan_table_high[j]), vh)
return fast_two_sum(s, se + (f64.bits(atan_table_low[j]) + (vl + series)))
## atan's Taylor coefficients from v³: -1/3, 1/5, -1/7, 1/9.
let atan_coefficients: f64[4] = [-0.3333333333333333, 0.2, -0.14285714285714285, 0.1111111111111111]
## atan(y/x) as a pair in [0, pi/2], for y and x positive with neither far from 1 (both
## within 2^±600 and their ratio within 2^±62), so every product stays exact.
inline func atan2_pair(y: f64, x: f64) -> (f64, f64):
if y <= x:
return atan_ratio(y, x)
let (h, l) = atan_ratio(x, y)
return add_pairs(f64.bits(pio2_high), f64.bits(pio2_low), -h, -l)
## The arctangent, in [-pi/2, pi/2].
func atan_accurate(x: f64) -> f64:
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude < 0x3e40000000000000:
# below 2^-27, x³/3 is under half an ulp of x: x itself, signed zero kept
return x
if magnitude >= 0x4410000000000000:
# from 2^66, pi/2 - 1/x rounds to pi/2's double
return x + x if x != x else copysign(f64.bits(pio2_high), x)
let a = f64.bits(magnitude)
let (h, l) = atan2_pair(a, 1.0)
return copysign(h + l, x)
## The angle of the point (x, y), in [-pi, pi], with Annex F's signed zeros and infinities.
func atan2_accurate(y: f64, x: f64) -> f64:
if x != x or y != y:
return x + y
let ay = abs(y)
let ax = abs(x)
let negative_x = signbit(x)
if ay == 0.0 or ax == infinity:
if ay == infinity:
# both infinite: a quarter or three quarters of pi
let angle = 2.356194490192345 if negative_x else 0.7853981633974483
return copysign(angle, y)
if negative_x:
return copysign(f64.bits(pi_high), y)
return copysign(0.0, y)
if ax == 0.0 or ay == infinity:
return copysign(f64.bits(pio2_high), y)
if ay > ax * 4.611686018427388e+18:
# |y/x| beyond 2^62: pi/2 less or plus a quotient too small for its series to matter
let t = ax / ay
return copysign(f64.bits(pio2_high) + (f64.bits(pio2_low) + (t if negative_x else -t)), y)
if ax > ay * 4.611686018427388e+18:
# |y/x| below 2^-62: atan is the quotient itself, rounded once
if not negative_x:
return copysign(ay / ax, y)
return copysign(f64.bits(pi_high) + (f64.bits(pi_low) - ay / ax), y)
# bring the larger into [2^-500, 2^500]; the smaller stays within 2^62 of it
var sy = ay
var sx = ax
let larger = ay if ay > ax else ax
if larger > 3.273390607896142e+150:
sy = sy * 2.409919865102884e-181
sx = sx * 2.409919865102884e-181
elif larger < 3.054936363499605e-151:
sy = sy * 4.149515568880993e+180
sx = sx * 4.149515568880993e+180
var angle = atan2_pair(sy, sx)
if negative_x:
angle = add_pairs(f64.bits(pi_high), f64.bits(pi_low), -angle.0, -angle.1)
return copysign(angle.0 + angle.1, y)
## P(z) less its constant term, for 0 <= z <= 1/4: Estrin's scheme, pairs and then pairs of
## pairs, for a shorter chain than Horner's.
inline func asin_series(z: f64) -> f64:
let k = asin_coefficients
let z2 = z * z
let z4 = z2 * z2
let p12 = k[1] + z * k[2]
let p34 = k[3] + z * k[4]
let p56 = k[5] + z * k[6]
let p78 = k[7] + z * k[8]
let p910 = k[9] + z * k[10]
let p1112 = k[11] + z * k[12]
let low = (p12 + z2 * p34) + z4 * (p56 + z2 * p78)
let high = (p910 + z2 * p1112) + z4 * k[13]
return z * (low + (z4 * z4) * high)
## asin w - w for 0 <= w <= 1/2, given z = w²: w·z·P(z), P fitted to (asin w - w)/w³.
inline func asin_tail(w: f64, z: f64) -> f64:
return w * z * (asin_coefficients[0] + asin_series(z))
## asin(wh + wl) as a pair less nothing, for w = sqrt(z) in [0, 1/2] given as a pair: the
## tail w·z·P(z) with w·z and its leading term kept exactly, as the result it feeds is
## pi/2 less twice it, where its errors would otherwise count double.
inline func asin_pair(wh: f64, wl: f64, z: f64) -> (f64, f64):
let (a, ae) = two_product(wh, z)
let (t, te) = two_product(a, asin_coefficients[0])
# asin(wh + wl) = asin wh + wl/sqrt(1 - z), the derivative's series to z³
let rest = te + ae * asin_coefficients[0] + a * asin_series(z) + wl * (1.0 + z * (0.5 + z * (0.375 + z * 0.3125)))
let (h, hl) = fast_two_sum(wh, t)
return fast_two_sum(h, hl + rest)
## The arcsine, in [-pi/2, pi/2]. Up to 1/2 it is x + x³·P(x²); beyond, fdlibm's
## pi/2 - 2·asin(w) for w = sqrt((1 - |x|)/2), whose square is exact and w a pair.
func asin_value(x: f64) -> f64:
let a = abs(x)
if not (a < 1.0):
if a == 1.0:
return copysign(f64.bits(pio2_high), x)
return (x - x) / (x - x)
if a < 1.4901161193847656e-08:
# below 2^-26, x³/6 is under half an ulp of x: x itself, signed zero kept
return x
if a <= 0.5:
return x + asin_tail(x, x * x)
let z = (1.0 - a) * 0.5
let (wh, wl) = pair_square_root(z, 0.0)
let (sh, sl) = asin_pair(wh, wl, z)
let (h, hl) = two_sum(f64.bits(pio2_high), -2.0 * sh)
return copysign(h + (hl + (f64.bits(pio2_low) - 2.0 * sl)), x)
## The arccosine, in [0, pi]: pi/2 - asin x up to 1/2; beyond, 2·asin(w) for
## w = sqrt((1 - x)/2), or pi less that for negative x.
func acos_value(x: f64) -> f64:
let a = abs(x)
if not (a < 1.0):
if x == 1.0:
return 0.0
if x == -1.0:
return f64.bits(pi_high)
return (x - x) / (x - x)
if a <= 0.5:
let (h, hl) = two_sum(f64.bits(pio2_high), -x)
return h + (hl + (f64.bits(pio2_low) - asin_tail(x, x * x)))
let z = (1.0 - a) * 0.5
let (wh, wl) = pair_square_root(z, 0.0)
let (sh, sl) = asin_pair(wh, wl, z)
if x > 0.0:
return 2.0 * (sh + sl)
let (h, hl) = two_sum(f64.bits(pi_high), -2.0 * sh)
return h + (hl + (f64.bits(pi_low) - 2.0 * sl))
# mark: The fast path =========================================================================
# atan and atan2 of magnitudes in [2^-500, 2^500] first try the same table with fused
# multiply-adds: for n <= d, c = j/64 nearest n/d, and v = (n - c·d)/(d + c·n) with both
# the numerator and the denominator exact pairs (fused products and two-sums) and the
# quotient's remainder by a fused multiply-add, so v is good to about 2^-100. atan c + v is
# an exact sum (atan c is zero or above 2^-6, |v| below 2^-7), and v³·S(v²), atan's series
# to v^9, is under 2^-22 of v and summed in doubles. The quadrant is a base of 0, pi/2 or pi
# and a sign, picked by selections; the base's sum is exact again.
#
# The error budget, relative to the result: the series' truncation (v^11/11 against v)
# 2^-80; its evaluation 2^-75; the table, the quotient and pi's parts 2^-99; four
# roundings of terms under 2^-22 of the result 2^-73; the quadrant's base adds at most a
# factor two, as pi/2 - a >= pi/4. Under 2^-71 in all; the test allows 2^-63 of h, so a
# fast return is the correctly rounded value.
## The bits of 2^-500, and the span from it to 2^500.
let atan_low_bits: u64 = 0x20b0000000000000
let atan_span_bits: u64 = 0x5f30000000000000 - 0x20b0000000000000
## atan(n/d) for 0 < n <= d as a pair.
inline func atan_ratio_fast(n: f64, d: f64) -> (f64, f64):
let jd = (n / d * 64.0 + round_shift) - round_shift
let c = jd * 0.015625
let (p, pe) = two_product(c, d)
let (nh, ne) = two_sum(n, -p)
let (q, qe) = two_product(c, n)
let (dh, de) = fast_two_sum(d, q)
let vh = nh / dh
let vl = ((-vh).mul_add(dh, nh) + ((ne - pe) - vh * (de + qe))) / dh
let z = vh * vh
let series = vh * z * z.mul_add(z.mul_add(z.mul_add(0.1111111111111111, -0.14285714285714285), 0.2), -0.3333333333333333)
let j = (usize)(i64)jd
let (h, he) = fast_two_sum(f64.bits(atan_table_high[j]), vh)
return (h, he + (f64.bits(atan_table_low[j]) + (vl + series)))
## Whether a magnitude is in the fast path's range.
inline func atan_in_range(a: f64) -> bool:
return a.bits() -% atan_low_bits < atan_span_bits
## The angle of (b, a) for a and b positive in range, as base + sign·atan(min/max): the
## quadrant of (x < 0, |y| > |x|) picks the base, 0, pi/2 or pi, and the sign.
inline func angle_fast(a: f64, b: f64, behind: bool) -> (f64, f64):
let swapped = a > b
let n = b if swapped else a
let d = a if swapped else b
let (h, l) = atan_ratio_fast(n, d)
let negate = swapped != behind
let half_h = f64.bits(pio2_high)
let half_l = f64.bits(pio2_low)
let whole_h = f64.bits(pi_high)
let whole_l = f64.bits(pi_low)
let behind_h = whole_h if behind else 0.0
let behind_l = whole_l if behind else 0.0
let base_h = half_h if swapped else behind_h
let base_l = half_l if swapped else behind_l
let sh = -h if negate else h
let sl = -l if negate else l
let (s, se) = two_sum(base_h, sh)
return (s, se + (base_l + sl))
func atan_value(x: f64) -> f64:
let a = abs(x)
if atan_in_range(a):
let (h, l) = angle_fast(a, 1.0, false)
if rounds_within_inverse(h, l):
return copysign(h + l, x)
return atan_accurate(x)
func atan2_value(y: f64, x: f64) -> f64:
let a = abs(y)
let b = abs(x)
if atan_in_range(a) and atan_in_range(b):
let (h, l) = angle_fast(a, b, x < 0.0)
if rounds_within_inverse(h, l):
return copysign(h + l, y)
return atan2_accurate(y, x)
## Whether h + l rounds the same at both ends of 2^-63 of h.
inline func rounds_within_inverse(h: f64, l: f64) -> bool:
let bound = abs(h) * 1.0842021724855044e-19
return h + (l - bound) == h + (l + bound)