dymokomi/luce-std
Source of release 0.7.4
0.7.4 / src / math / trig.lucb
#==============================================================================================
#
# trig - sin, cos, sincos and tan, and the reduction of an argument by pi/2
#
# DESCRIPTION:
# sin, cos and tan below 2^20 first try the table method at the end of this file,
# which returns only results it proves correctly rounded. Everything else takes the
# accurate method. That method is fdlibm's (Sun's, as in FreeBSD and musl): x = n·pi/2 + r with r as a
# pair, |r| <= pi/4, then sin or cos of r by its series, picked and signed by n mod 4.
# Below 2^20·pi/2 the reduction is Cody and Waite's, with pi/2 in three 33-bit parts
# and a fourth, so n times each of the first three is exact and the error stays near
# 2^-131. Above that it is Payne and Hanek's: the 53-bit integer of x times a window of
# 2/pi's bits, in 32-bit words, gives n mod 8 and the fraction to beyond 2^-160, as
# fdlibm's __kernel_rem_pio2 does with floats. sin and cos of r are their Taylor series
# to r^19 and r^20, below 2^-72; tan is their quotient as pairs. Written anew from the
# method; 2/pi's bits come from tools/math_tables.py.
#
#==============================================================================================
## The bits of x's magnitude below which r is x itself (pi/4), and below which the
## Cody-Waite reduction's n fits in 20 bits (2^20·pi/2).
let quarter_pi_bits: u64 = 0x3fe921fb54442d18
let cody_waite_bits: u64 = 0x413921fb54442d18
## 64 bits of the little-endian 32-bit words `words`, from bit `position` up.
func bits_at(words: u32[], position: usize) -> u64:
let w = position // 32
let offset = (u64)(position % 32)
let low = (u64)words[w] | ((u64)words[w + 1] << 32)
if offset == 0:
return low
let high = (u64)words[w + 2] | ((u64)words[w + 3] << 32)
return (low >> offset) | (high << (64 - offset))
## x = n·pi/2 + r for |x| >= 2^20·pi/2, finite: n mod 4 and r as a pair (Payne-Hanek).
func reduce_large(x: f64) -> (i64, f64, f64):
let ix = x.bits()
let exponent = (i64)((ix >> 52) & 0x7ff) - 1075
let m = (ix & 0x000fffffffffffff) | 0x0010000000000000
# Words of 2/pi before `first` contribute multiples of 8 to x·2/pi: m·2^exponent times a
# bit worth 2^-i is a multiple of 8 when i <= exponent - 3.
let first = (usize)((exponent - 3) // 32) if exponent >= 3 else 0
let count: usize = 8
var product: u64[12]
let m_low = m & 0xffffffff
let m_high = m >> 32
for j in 0..<count:
# word j of the window, counted from its least significant end
let word = (u64)two_over_pi[first + count - 1 - j]
let low_part = m_low * word
let high_part = m_high * word
product[j] += low_part & 0xffffffff
product[j + 1] += (low_part >> 32) + (high_part & 0xffffffff)
product[j + 2] += high_part >> 32
# four words of zeros past the product, for bits_at's reads
var words: u32[16]
var carry: u64 = 0
for c in 0..<12:
let total = product[c] + carry
words[c] = (u32)(total & 0xffffffff)
carry = total >> 32
# x·2/pi = product·2^-shift; the bits at and above `shift` are the integer part
let shift = (usize)((i64)(32 * (first + count)) - exponent)
var n = (i64)(bits_at(words, shift) & 7)
let f0 = bits_at(words, shift - 64)
let f1 = bits_at(words, shift - 128)
let f2 = bits_at(words, shift - 192)
# the fraction as a pair, from exact pieces of at most 53 bits, largest first
let pieces: f64[5] = [(f64)(f0 >> 11) * 1.1102230246251565e-16, (f64)(f0 & 0x7ff) * 5.421010862427522e-20, (f64)(f1 >> 11) * 6.018531076210112e-36, (f64)(f1 & 0x7ff) * 2.938735877055719e-39, (f64)(f2 >> 11) * 3.2626522339992623e-55]
var fh: f64 = 0.0
var fl: f64 = 0.0
for piece in pieces:
let (s, t) = two_sum(fh, piece)
fh = s
fl += t
if f0 >> 63 == 1:
# past one half: the nearer multiple is the next, and r is negative
n += 1
let (s, t) = two_sum(fh, -1.0)
fh = s
fl += t
let (rh, rl) = multiply_pairs(fh, fl, f64.bits(pio2_high), f64.bits(pio2_low))
if ix >> 63 == 1:
return (-n, -rh, -rl)
return (n, rh, rl)
## x = n·pi/2 + r for finite x: n (its low two bits are what matter) and r as a pair with
## |r| <= pi/4 or a hair beyond.
inline func reduce_half_pi(x: f64) -> (i64, f64, f64):
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude <= quarter_pi_bits:
return (0, x, 0.0)
if magnitude >= cody_waite_bits:
return reduce_large(x)
let nd = (x * f64.bits(two_over_pi_double) + round_shift) - round_shift
let a = x - nd * f64.bits(pio2_1)
let (s1, e1) = two_sum(a, -(nd * f64.bits(pio2_2)))
let (s2, e2) = two_sum(s1, -(nd * f64.bits(pio2_3)))
let (rh, rl) = fast_two_sum(s2, (e1 + e2) - nd * f64.bits(pio2_4))
return ((i64)nd, rh, rl)
## sin's Taylor coefficients from r^5: 1/5!, -1/7!, ..., -1/19!.
let sin_coefficients: f64[8] = [0.008333333333333333, -0.0001984126984126984, 2.7557319223985893e-06, -2.505210838544172e-08, 1.6059043836821613e-10, -7.647163731819816e-13, 2.8114572543455206e-15, -8.22063524662433e-18]
## cos's Taylor coefficients from r^4: 1/4!, -1/6!, ..., 1/20!.
let cos_coefficients: f64[9] = [0.041666666666666664, -0.001388888888888889, 2.48015873015873e-05, -2.755731922398589e-07, 2.08767569878681e-09, -1.1470745597729725e-11, 4.779477332387385e-14, -1.5619206968586225e-16, 4.110317623312165e-19]
## 1/6 as a double and the double nearest its remainder.
let sixth_high: f64 = 0.16666666666666666
let sixth_low: f64 = 9.25185853854297e-18
## sin(rh + rl) for |r| <= pi/4, as a pair: rh - rh³/6 with the cube and the sixth kept as
## pairs, then rh^5·S(rh²), S the Taylor series of (sin r - r + r³/6)/r^5 to r^14, and
## rl·cos(rh).
inline func sin_pair(rh: f64, rl: f64) -> (f64, f64):
let (zh, zl) = two_square(rh)
let (ch, ce) = two_product(rh, zh)
let (th, te) = two_product(ch, sixth_high)
let (s, se) = fast_two_sum(rh, -th)
let k = sin_coefficients
let series = k[0] + zh * (k[1] + zh * (k[2] + zh * (k[3] + zh * (k[4] + zh * (k[5] + zh * (k[6] + zh * k[7]))))))
let tail = (ce + rh * zl) * sixth_high + ch * sixth_low
return fast_two_sum(s, (se - (te + tail)) + (rl * (1.0 - 0.5 * zh) + rh * zh * zh * series))
## cos(rh + rl) for |r| <= pi/4, as a pair: 1 - r²/2 with r² exact and the subtraction's
## error kept, then r^4·C(r²), C the Taylor series of (cos r - 1 + r²/2)/r^4 to r^16.
inline func cos_pair(rh: f64, rl: f64) -> (f64, f64):
let (zh, zl) = two_square(rh)
let half = 0.5 * zh
let (w, we) = fast_two_sum(1.0, -half)
let k = cos_coefficients
let series = k[0] + zh * (k[1] + zh * (k[2] + zh * (k[3] + zh * (k[4] + zh * (k[5] + zh * (k[6] + zh * (k[7] + zh * k[8])))))))
return fast_two_sum(w, (we - 0.5 * (zl + 2.0 * rh * rl)) + zh * zh * series)
## sin x, picked from sin r and cos r by n mod 4.
func sin_accurate(x: f64) -> f64:
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude < 0x3e50000000000000:
# below 2^-26, x³/6 is under half an ulp of x: x itself, signed zero kept
return x
if magnitude >= 0x7ff0000000000000:
return x - x
let (n, rh, rl) = reduce_half_pi(x)
let quadrant = n & 3
let (h, l) = cos_pair(rh, rl) if quadrant & 1 == 1 else sin_pair(rh, rl)
return -(h + l) if quadrant >= 2 else h + l
## cos x, picked from cos r and sin r by n mod 4.
func cos_accurate(x: f64) -> f64:
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude < 0x3e40000000000000:
# below 2^-27, x²/2 is under half an ulp of 1
return 1.0
if magnitude >= 0x7ff0000000000000:
return x - x
let (n, rh, rl) = reduce_half_pi(x)
let quadrant = n & 3
let (h, l) = sin_pair(rh, rl) if quadrant & 1 == 1 else cos_pair(rh, rl)
return -(h + l) if quadrant == 1 or quadrant == 2 else h + l
## tan x: sin r / cos r as pairs, or -cos r / sin r for odd n.
func tan_accurate(x: f64) -> f64:
let magnitude = x.bits() & 0x7fffffffffffffff
if magnitude < 0x3e40000000000000:
# below 2^-27, x³/3 is under half an ulp of x
return x
if magnitude >= 0x7ff0000000000000:
return x - x
let (n, rh, rl) = reduce_half_pi(x)
let (sh, sl) = sin_pair(rh, rl)
let (ch, cl) = cos_pair(rh, rl)
if n & 1 == 1:
let (h, l) = divide_pairs(ch, cl, sh, sl)
return -(h + l)
let (h, l) = divide_pairs(sh, sl, ch, cl)
return h + l
# mark: The table method ======================================================================
# For 2^-27 <= |x| < 2^20, sin and cos first try a shorter road: x = n·pi/128 + r with
# |r| <= pi/256, and sin x = A·cos r + B·sin r for A = sin(n·pi/128) and B = cos(n·pi/128)
# from a table of double-double values (as IBM's libultim and CORE-MATH do). B·r is exact
# (Dekker's product) and so is A + B·r; the rest, A·(cos r - 1) + B·(sin r - r) and the low
# parts, is under 2^-13 of A and is summed in doubles.
#
# The error budget, u = 2^-53. The reduction: n·step_1 and n·step_2 are exact and so is x
# less the first (Sterbenz); what step_3 and its product leave is below 2^-86 absolute for
# n < 2^26. The rest is relative to |A|: A·(cos r - 1) is at most 2^-13.7·|A| and carries
# at most 7u of it from z, the series, the product and three sums, 2^-63.9·|A|; the series'
# truncation adds 2^-66.1·|A|, the table's 2^-106, and the terms in rl, B's low part and t
# below 2^-70 of the result. With n·pi/128 not a multiple of pi, |A| >= sin(pi/128) is at
# least twice |B·r|, so |A| <= 2·|sin x|; otherwise A is 0 and so are those terms. The
# total stays under 2^-62.3·|result| + 2^-86, and the test below allows 2^-61·|h| + 2^-85,
# h being within 2^-12 of the result. Rounding is monotonic, so when h + (l - bound) and
# h + (l + bound) round to the same double, the exact value rounds to it too: a value
# returned here is the correctly rounded one. The others, about one in two hundred, go to
# the method above.
## The bits of 2^-27, and the span of bits from it to 2^20: one unsigned comparison tells
## whether |x| is in the table method's range, where n stays below 2^26.
let fast_trig_low: u64 = 0x3e40000000000000
let fast_trig_span: u64 = 0x4130000000000000 - 0x3e40000000000000
## x = n·pi/128 + rh + rl, with pi/128 in three parts whose first two times n are exact.
inline func reduce_step(x: f64) -> (i64, f64, f64):
let kd = (x * f64.bits(inverse_step) + round_shift) - round_shift
let a = x - kd * f64.bits(step_1)
let (r0, e0) = two_sum(a, -(kd * f64.bits(step_2)))
let (rh, rl) = fast_two_sum(r0, e0 - kd * f64.bits(step_3))
return ((i64)kd, rh, rl)
## cos r - 1 and sin r - r from z = r², their Taylor series to r^6 and r^7, below 2^-75.
inline func cos_less_one(z: f64) -> f64:
return z * (-0.5 + z * (0.041666666666666664 + z * -0.001388888888888889))
inline func sin_less_r(rh: f64, z: f64) -> f64:
return rh * z * (-0.16666666666666666 + z * (0.008333333333333333 + z * -0.0001984126984126984))
## The table's entry k (mod 256), sin(k·pi/128), as its two parts.
inline func sine_entry(k: i64) -> (f64, f64):
let i = (usize)(k & 255) * 2
return (f64.bits(sine_table[i]), f64.bits(sine_table[i + 1]))
## A·cos r + B·sin r as h + l, for A and B entries of the table: A + B·rh exactly, the rest
## in a double. l is below 2^-12 of h.
inline func rotate(ah: f64, al: f64, bh: f64, bl: f64, rh: f64, rl: f64, c: f64, t: f64) -> (f64, f64):
let (ph, pl) = two_product(bh, rh)
let (h, he) = fast_two_sum(ah, ph)
return (h, (he + pl) + (al + bl * rh) + rl * (bh - ah * rh) + (ah * c + bh * t))
## Whether h + l rounds the same at both ends of its error bound: 2^-61 of h, and 2^-85
## for what the reduction leaves out.
inline func rounds_alike(h: f64, l: f64) -> bool:
let bound = abs(h) * 4.336808689942018e-19 + 2.5849394142282115e-26
return h + (l - bound) == h + (l + bound)
## Whether the table method takes x: 2^-27 <= |x| < 2^20.
inline func trig_inside(x: f64) -> bool:
return (x.bits() & 0x7fffffffffffffff) -% fast_trig_low < fast_trig_span
## sin x by the table method as h + l; any x runs through it without a trap.
inline func sin_parts(x: f64) -> (f64, f64):
let (n, rh, rl) = reduce_step(x)
let z = rh * rh
let (ah, al) = sine_entry(n)
let (bh, bl) = sine_entry(n +% 64)
return rotate(ah, al, bh, bl, rh, rl, cos_less_one(z), sin_less_r(rh, z))
## cos x as sin x but from the entries a quarter turn on: cos(a + r) = B·cos r - A·sin r.
inline func cos_parts(x: f64) -> (f64, f64):
let (n, rh, rl) = reduce_step(x)
let z = rh * rh
let (ah, al) = sine_entry(n +% 64)
let (bh, bl) = sine_entry(n +% 128)
return rotate(ah, al, bh, bl, rh, rl, cos_less_one(z), sin_less_r(rh, z))
## sin x and cos x from one reduction and one pair of entries, each as h + l.
inline func sincos_parts(x: f64) -> (f64, f64, f64, f64):
let (n, rh, rl) = reduce_step(x)
let z = rh * rh
let c = cos_less_one(z)
let t = sin_less_r(rh, z)
let (ah, al) = sine_entry(n)
let (bh, bl) = sine_entry(n +% 64)
let (sh, sl) = rotate(ah, al, bh, bl, rh, rl, c, t)
let (ch, cl) = rotate(bh, bl, -ah, -al, rh, rl, c, t)
return (sh, sl, ch, cl)
## sin x: the table method when it vouches for its rounding, else sin_accurate.
func sin_value(x: f64) -> f64:
if trig_inside(x):
let (h, l) = sin_parts(x)
if rounds_alike(h, l):
return h + l
return sin_accurate(x)
## cos x: the table method when it vouches for its rounding, else cos_accurate.
func cos_value(x: f64) -> f64:
if trig_inside(x):
let (h, l) = cos_parts(x)
if rounds_alike(h, l):
return h + l
return cos_accurate(x)
## sin x and cos x from one reduction and one pair of entries.
func sincos_value(x: f64) -> (f64, f64):
if trig_inside(x):
let (sh, sl, ch, cl) = sincos_parts(x)
if rounds_alike(sh, sl) and rounds_alike(ch, cl):
return (sh + sl, ch + cl)
return (sin_value(x), cos_value(x))
## tan x as the quotient of the table method's sin x and cos x, each within 2^-62.3 of
## itself plus 2^-86, with its remainder by a fused multiply-add. Where both are at least
## 2^-20 that is within 2^-61.2 of tan x; the test allows 2^-60. Near a multiple of pi/2,
## and for the inputs the test turns down, tan_accurate.
func tan_value(x: f64) -> f64:
if trig_inside(x):
# rotate's low parts reach 2^-13 of the high ones: renormalize before dividing
let (s0, s1, c0, c1) = sincos_parts(x)
let (sh, sl) = fast_two_sum(s0, s1)
let (ch, cl) = fast_two_sum(c0, c1)
if abs(sh) >= 9.5367431640625e-07 and abs(ch) >= 9.5367431640625e-07:
let qh = sh / ch
let ql = ((-qh).mul_add(ch, sh) + (sl - qh * cl)) / ch
let bound = abs(qh) * 8.673617379884035e-19
if qh + (ql - bound) == qh + (ql + bound):
return qh + ql
return tan_accurate(x)