dymokomi/luce-std
Source of release 0.7.3
#==============================================================================================
#
# log - The logarithms: log, log2, log10, log1p, and log x as a pair for pow
#
# DESCRIPTION:
# log, log2 and log10 of normal x 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 logarithm, with the interval selection of ARM's
# optimized-routines (as in musl): x = 2^k·z with z in [0.6875, 1.375), whose top
# mantissa bits pick one of 128 intervals and its point F (the midpoint, or 1 beside 1),
# so log x = k·ln2 + log F + log1p(u) for u = (z - F)/F, |u| <= 2^-7. z - F is exact,
# u is formed with its remainder, and log1p(u)'s square term is kept exactly; the rest
# is the Taylor series to u^10, below 2^-73 of u. Written anew from the method; the
# tables come from tools/math_tables.py. log x comes out as a pair good to about
# 2^-68, so every logarithm here rounds once from it.
#
#==============================================================================================
## The bits of 0.6875: x's bits less these give k in the exponent field and the interval
## in the top seven mantissa bits.
let log_offset: u64 = 0x3fe6000000000000
## log1p's Taylor coefficients from u³: 1/3, -1/4, ..., -1/10. Read from memory, as each
## constant written in an expression costs several instructions to build.
let log_coefficients: f64[8] = [0.3333333333333333, -0.25, 0.2, -0.16666666666666666, 0.14285714285714285, -0.125, 0.1111111111111111, -0.1]
## The interval whose point F is 1, where u is z - 1 itself.
let log_interval_one: usize = 80
## log x as a pair, for x positive, finite and nonzero, subnormals included.
inline func log_pair(x: f64) -> (f64, f64):
var ix = x.bits()
var k: i64 = 0
if ix < 0x0010000000000000:
ix = (x * 4503599627370496.0).bits()
k = -52
let shifted = ix -% log_offset
let i = (usize)((shifted >> 45) & 127)
k += (i64)shifted >> 52
let z = f64.bits(ix -% (shifted & 0xfff0000000000000))
let point = f64.bits(log_point[i])
let inverse = f64.bits(log_inverse[i])
# u = f/F with its remainder: F has at most nine bits, so each half of uh times F is exact
let f = z - point
let uh = f * inverse
let (uhh, uhl) = split(uh)
let ul = ((f - uhh * point) - uhl * point) * inverse
return log_series((f64)k, i, uh, ul)
## k·ln2 + log F + log1p(uh + ul) as a pair, F the point of interval `i`.
## log1p(u) = u - u²/2 + u³/3 - ...: -u²/2 exactly, with the cross term -uh·ul.
inline func log_series(kd: f64, i: usize, uh: f64, ul: f64) -> (f64, f64):
let (square, square_error) = two_square(uh)
let base = kd * f64.bits(ln2_high) + f64.bits(log_table_high[i])
let (s1, e1) = fast_two_sum(base, uh)
let (s2, e2) = fast_two_sum(s1, -0.5 * square)
let k = log_coefficients
let series = uh * square * (k[0] + uh * (k[1] + uh * (k[2] + uh * (k[3] + uh * (k[4] + uh * (k[5] + uh * (k[6] + uh * k[7])))))))
let low = kd * f64.bits(ln2_low) + f64.bits(log_table_low[i])
return fast_two_sum(s2, ((e1 + e2) + (ul - 0.5 * square_error - uh * ul)) + (low + series))
## Whether x is outside the positive finite numbers, where `log_special` answers.
inline func log_is_special(x: f64) -> bool:
return x.bits() -% 1 >= 0x7fefffffffffffff
## The special values every logarithm shares: NaN for NaN and negative x, -infinity for
## zero, +infinity for +infinity.
func log_special(x: f64) -> f64:
let ix = x.bits()
if x != x:
return x + x
if ix & 0x7fffffffffffffff == 0:
return f64.bits(0xfff0000000000000)
if ix == 0x7ff0000000000000:
return x
return f64.bits(0x7ff8000000000000)
## The natural logarithm.
func log_accurate(x: f64) -> f64:
if log_is_special(x):
return log_special(x)
let (h, l) = log_pair(x)
return h + l
## The logarithm to base 2: log x times 1/ln2, both pairs. A power of two gives its exponent.
func log2_accurate(x: f64) -> f64:
if log_is_special(x):
return log_special(x)
let (h, l) = log_pair(x)
let (p, q) = multiply_pairs(h, l, f64.bits(log2_e_high), f64.bits(log2_e_low))
return p + q
## The logarithm to base 10: log x times 1/ln10, both pairs.
func log10_accurate(x: f64) -> f64:
if log_is_special(x):
return log_special(x)
let (h, l) = log_pair(x)
let (p, q) = multiply_pairs(h, l, f64.bits(log10_e_high), f64.bits(log10_e_low))
return p + q
## log(1 + x): below 2^-7 the series in x itself; above, 1 + x as a rounded sum and its exact
## error c, then log of the sum plus c/sum, where c is too small for its rounding to matter.
func log1p_value(x: f64) -> f64:
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 not (x > -1.0) or magnitude >= 0x7ff0000000000000:
if x != x or x == f64.bits(0x7ff0000000000000):
return x + x
if x == -1.0:
return f64.bits(0xfff0000000000000)
return f64.bits(0x7ff8000000000000)
if magnitude < 0x3f80000000000000:
# below 2^-7, x is u itself: the series with F = 1 and nothing rounded away
let (h, l) = log_series(0.0, log_interval_one, x, 0.0)
return h + l
let (s, c) = two_sum(1.0, x)
let (h, l) = log_pair(s)
return h + (l + c / s)
# mark: The fast path =========================================================================
# For normal x, log, log2 and log10 first try the same reduction with fused multiply-adds:
# u = (z - F)/F as uh + ul, with z - F exact and ul from the remainder f - uh·F, which a
# fused multiply-add gives exactly (uh·F needs 62 bits, and the remainder is within 10
# bits of the last of them). k·ln2_high + log F is exact, and is zero or larger than u
# (beside 1, F is 1; one interval on, |log F| >= 2^-7.4 against |u| <= 2^-8), so adding
# uh keeps its error by Dekker's fast two-sum. u² is exact as a pair, and what remains
# (u³·Q(u), the cross terms and the low parts) is under 2^-20 of the result and summed in
# doubles.
#
# The error budget, relative to the result: Q's truncation (u^10/11 against u) 2^-73; its
# evaluation, under 2^-53 of u³/3, 2^-75; the dropped ul² and ul·u² 2^-104; the rounding of
# the remainder's quotient 2^-106; five roundings in the low sum, each under 2^-53 of 2^-20
# of the result, 2^-71; the tables' and ln2_low's representation 2^-95. Under 2^-70 in
# all; the test allows 2^-63 of h (log2 and log10 2^-62, their constants and products
# adding 2^-104), so a fast return is the correctly rounded value. Inputs within 2^-63 of a
# rounding boundary, subnormals, zero, negative x, infinity and NaN take the method above.
## log1p(u) - u + u²/2 for |u| <= 2^-7: u³·Q(u), Q the Taylor series from 1/3 to -1/10.
inline func log_series_fast(u: f64) -> f64:
let u2 = u * u
let p01 = u.mul_add(-0.25, 0.3333333333333333)
let p23 = u.mul_add(-0.16666666666666666, 0.2)
let p45 = u.mul_add(-0.125, 0.14285714285714285)
let p67 = u.mul_add(-0.1, 0.1111111111111111)
let q = (u2 * u2).mul_add(u2.mul_add(p67, p45), u2.mul_add(p23, p01))
return u * u2 * q
## log x as h + l for x positive, normal and finite.
inline func log_fast(x: f64) -> (f64, f64):
let ix = x.bits()
let shifted = ix -% log_offset
let i = (usize)((shifted >> 45) & 127)
let kd = (f64)((i64)shifted >> 52)
let z = f64.bits(ix -% (shifted & 0xfff0000000000000))
let point = f64.bits(log_point[i])
let inverse = f64.bits(log_inverse[i])
let f = z - point
let uh = f * inverse
let ul = (-uh).mul_add(point, f) * inverse
let (s1, e1) = fast_two_sum(kd * f64.bits(ln2_high) + f64.bits(log_table_high[i]), uh)
let (q, qe) = two_square(uh)
let (h, e2) = fast_two_sum(s1, -0.5 * q)
let low = kd * f64.bits(ln2_low) + f64.bits(log_table_low[i])
return (h, ((e1 + e2) + low) + ((ul - uh * ul - 0.5 * qe) + log_series_fast(uh)))
## Whether x is positive, normal and finite.
inline func log_is_normal(x: f64) -> bool:
return x.bits() -% 0x0010000000000000 < 0x7fe0000000000000
## Whether h + l rounds the same at both ends of `relative`·|h|.
inline func rounds_within(h: f64, l: f64, relative: f64) -> bool:
let bound = abs(h) * relative
return h + (l - bound) == h + (l + bound)
## The natural logarithm: the fast path when it vouches for its rounding, else log_accurate.
func log_value(x: f64) -> f64:
if log_is_normal(x):
let (h, l) = log_fast(x)
if rounds_within(h, l, 1.0842021724855044e-19):
return h + l
return log_accurate(x)
## log x times 1/ln2 as a pair.
func log2_value(x: f64) -> f64:
if log_is_normal(x):
let (h, l) = log_fast(x)
let (p, q) = multiply_pairs(h, l, f64.bits(log2_e_high), f64.bits(log2_e_low))
if rounds_within(p, q, 2.168404344971009e-19):
return p + q
return log2_accurate(x)
## log x times 1/ln10 as a pair.
func log10_value(x: f64) -> f64:
if log_is_normal(x):
let (h, l) = log_fast(x)
let (p, q) = multiply_pairs(h, l, f64.bits(log10_e_high), f64.bits(log10_e_low))
if rounds_within(p, q, 2.168404344971009e-19):
return p + q
return log10_accurate(x)