Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-std

Source of release 0.7.5

0.7.5 / src / math / roots.lucb

#==============================================================================================
#
#   roots - cbrt and hypot
#
#   DESCRIPTION:
#       hypot first tries the fast path at the end of this file, which returns only results
#       it proves correctly rounded. cbrt follows fdlibm's plan: a first guess, an iteration to about 2^-40, then one
#       Newton step from the exact residual A - y³ (y³ as a pair), so the result rounds once
#       from an error near 2^-80. Here the guess is a cubic in the mantissa times a table's
#       cube root of 2^(exponent mod 3), and the iteration is Halley's. hypot squares both arguments exactly as pairs (Dekker),
#       adds them, and takes the root with its residual correction, as the correctly rounded
#       hypot of Borges ("An Improved Algorithm for hypot(a, b)", 2019) does; arguments are
#       scaled by 2^±600 first so that no square overflows or underflows. The special cases
#       are C99 Annex F.9.4's. Written anew from the method.
#
#==============================================================================================

## The cube roots of 1, 2 and 4.
let cube_roots: f64[3] = [1.0, 1.2599210498948732, 1.5874010519681996]

## The real cube root, odd, exact for perfect cubes.
func cbrt_value(x: f64) -> f64:
    var bits = x.bits() & 0x7fffffffffffffff
    if bits == 0 or bits >= 0x7ff0000000000000:
        # zeros and infinities are their own roots; NaN stays NaN
        return x + x
    var scale: i64 = 0
    if bits < 0x0010000000000000:
        # subnormal: 2^54 makes it normal, and 2^18 comes back off the root
        bits = (f64.bits(bits) * 18014398509481984.0).bits()
        scale = -18
    # x = m·2^(3q + rest) with m in [1, 2): the biased exponent's third and remainder, by a
    # multiply that divides by 3 below 2^17 (1023 being a multiple of 3, the bias drops out)
    let biased = bits >> 52
    let third = (biased * 43691) >> 17
    let rest = biased - 3 * third
    scale += (i64)third - 341
    let m = f64.bits((bits & 0x000fffffffffffff) | 0x3ff0000000000000)
    let big_a = m * f64.bits((u64)(rest + 1023) << 52)
    # a cubic in m within 1e-4 of cbrt m, times cbrt(2^rest); Halley's step
    # y·(y³ + 2A)/(2y³ + A) cubes the error to about 1e-12
    var y = (0.5557909602691388 + m * (0.5808263911380952 + m * (-0.1586624600531909 + m * 0.022148699208245196))) * cube_roots[(usize)rest]
    let cube = y * y * y
    y = y * (cube + 2.0 * big_a) / (2.0 * cube + big_a)
    # one Newton step from the exact residual A - y³ (y³ as a pair) squares that to 1e-24
    let (sh, sl) = two_square(y)
    let (ch, cl) = multiply_pairs(sh, sl, y, 0.0)
    let residual = (big_a - ch) - cl
    return copysign((y + residual / (3.0 * sh)) * power_of_two(scale), x)

## sqrt(x² + y²) without overflow or underflow in the squares, within half an ulp and a
## hair; an infinite argument gives +infinity even beside NaN.
func hypot_accurate(x: f64, y: f64) -> f64:
    var a = abs(x)
    var b = abs(y)
    if a == infinity or b == infinity:
        return infinity
    if a != a or b != b:
        return x + y
    if b > a:
        let t = a
        a = b
        b = t
    if b == 0.0 or a > b * 4.611686018427388e+18:
        # beyond 2^62 apart, b²/2a is under 2^-125 of a: the sum rounds as hypot does
        return a + b
    var scale: i64 = 0
    if a > 3.273390607896142e+150:
        a = a * 2.409919865102884e-181
        b = b * 2.409919865102884e-181
        scale = 600
    elif b < 3.054936363499605e-151:
        a = a * 4.149515568880993e+180
        b = b * 4.149515568880993e+180
        scale = -600
    let (ah, al) = two_square(a)
    let (bh, bl) = two_square(b)
    let (sh, sl) = add_pairs(ah, al, bh, bl)
    let (rh, rl) = pair_square_root(sh, sl)
    if scale == 0:
        return rh + rl
    # back by 2^±600 through scale_pair, which rounds a subnormal result once
    let exponent = (i64)(rh.bits() >> 52) - 1023
    let down = power_of_two(-exponent)
    return scale_pair(rh * down, rl * down, exponent + scale)

# mark: The fast path =========================================================================

# hypot with the larger magnitude in [2^-500, 2^500]: both squares exact as pairs by fused
# multiply-adds (the smaller's error is negligible even where it underflows), their sum
# with its error kept, and the root of the sum corrected by the exact residual s - r², a
# fused multiply-add: Borges's method without the scaling. The pair is within 2^-100 of the
# hypotenuse; the test allows 2^-63 of it, so a fast return is the correctly rounded value.

func hypot_value(x: f64, y: f64) -> f64:
    let a = abs(x)
    let b = abs(y)
    let swap = b > a
    let large = b if swap else a
    let small = a if swap else b
    if large.bits() -% 0x20b0000000000000 < 0x5f30000000000000 - 0x20b0000000000000:
        let (lh, ll) = two_square(large)
        let (sh, sl) = two_square(small)
        let (q, qe) = fast_two_sum(lh, sh)
        let ql = qe + (ll + sl)
        let r = c_sqrt(q)
        let rl = ((-r).mul_add(r, q) + ql) / (r + r)
        let bound = r * 1.0842021724855044e-19
        if r + (rl - bound) == r + (rl + bound):
            return r + rl
    return hypot_accurate(x, y)