dymokomi/luce-base
Source of release 0.43.0
0.43.0 / src / std / float_text / ryu.lucb
#==============================================================================================
#
# ryu - The shortest digits of a float (float_text)
#
# DESCRIPTION:
# Ryu's d2d and f2s over float_text's tables of powers of five: the fewest decimal
# digits, and their power of ten, that read back as a finite nonzero f64 or f32.
#
#==============================================================================================
# mark: Ryu ====================================================================================
## Ryu's d2d: the shortest decimal digits * 10^exponent of a finite, nonzero f64, given its
## mantissa and exponent fields.
func shortest64(ieee_mantissa: u64, ieee_exponent: u32) -> (u64, i32):
var e2: i32 = 0
var m2: u64 = 0
if ieee_exponent == 0:
e2 = 1 - 1023 - 52 - 2
m2 = ieee_mantissa
else:
e2 = (i32)ieee_exponent - 1023 - 52 - 2
m2 = ((u64)1 << 52) | ieee_mantissa
let accept_bounds = (m2 & 1) == 0
let mv = 4 * m2
let mm_shift: u64 = 1 if ieee_mantissa != 0 or ieee_exponent <= 1 else 0
var vr: u64 = 0
var vp: u64 = 0
var vm: u64 = 0
var e10: i32 = 0
var vm_trailing_zeros = false
var vr_trailing_zeros = false
if e2 >= 0:
let q = log10_pow2(e2) - (1 if e2 > 3 else 0)
e10 = q
let k = 125 + pow5_bits(q) - 1
let i = -e2 + q + k
let row = (usize)q * 2
vr = mul_shift64(4 * m2, pow5_inv_split[row], pow5_inv_split[row + 1], i)
vp = mul_shift64(4 * m2 + 2, pow5_inv_split[row], pow5_inv_split[row + 1], i)
vm = mul_shift64(4 * m2 - 1 - mm_shift, pow5_inv_split[row], pow5_inv_split[row + 1], i)
if q <= 21:
if mv % 5 == 0:
vr_trailing_zeros = pow5_factor(mv) >= (u32)q
elif accept_bounds:
vm_trailing_zeros = pow5_factor(mv - 1 - mm_shift) >= (u32)q
elif pow5_factor(mv + 2) >= (u32)q:
vp -= 1
else:
let q = log10_pow5(-e2) - (1 if -e2 > 1 else 0)
e10 = q + e2
let i = -e2 - q
let k = pow5_bits(i) - 125
let j = q - k
let row = (usize)i * 2
vr = mul_shift64(4 * m2, pow5_split[row], pow5_split[row + 1], j)
vp = mul_shift64(4 * m2 + 2, pow5_split[row], pow5_split[row + 1], j)
vm = mul_shift64(4 * m2 - 1 - mm_shift, pow5_split[row], pow5_split[row + 1], j)
if q <= 1:
vr_trailing_zeros = true
if accept_bounds:
vm_trailing_zeros = mm_shift == 1
else:
vp -= 1
elif q < 63:
vr_trailing_zeros = (mv & (((u64)1 << (u64)q) - 1)) == 0
return trimmed(vr, vp, vm, e10, accept_bounds, vm_trailing_zeros, vr_trailing_zeros, 0)
## Ryu's digit removal, d2d's and f2s's alike: drop digits while the bounds still differ,
## then round on the last digit removed (`start_last`, the one f2s's bounds computation
## already dropped, or 0). Dropping two digits at once leaves their tens digit as the last.
func trimmed(start_vr: u64, start_vp: u64, start_vm: u64, e10: i32, accept_bounds: bool, start_vm_zeros: bool, start_vr_zeros: bool, start_last: u64) -> (u64, i32):
var vr = start_vr
var vp = start_vp
var vm = start_vm
var vm_trailing_zeros = start_vm_zeros
var vr_trailing_zeros = start_vr_zeros
var removed: i32 = 0
var last_removed = start_last
if vm_trailing_zeros or vr_trailing_zeros:
while vp // 10 > vm // 10:
vm_trailing_zeros = vm_trailing_zeros and vm % 10 == 0
vr_trailing_zeros = vr_trailing_zeros and last_removed == 0
last_removed = vr % 10
vr = vr // 10
vp = vp // 10
vm = vm // 10
removed += 1
if vm_trailing_zeros:
while vm % 10 == 0:
vr_trailing_zeros = vr_trailing_zeros and last_removed == 0
last_removed = vr % 10
vr = vr // 10
vp = vp // 10
vm = vm // 10
removed += 1
if vr_trailing_zeros and last_removed == 5 and vr % 2 == 0:
last_removed = 4
let up = (vr == vm and (not accept_bounds or not vm_trailing_zeros)) or last_removed >= 5
return (vr + (1 if up else 0), e10 + removed)
if vp // 100 > vm // 100:
last_removed = (vr % 100) // 10
vr = vr // 100
vp = vp // 100
vm = vm // 100
removed += 2
while vp // 10 > vm // 10:
last_removed = vr % 10
vr = vr // 10
vp = vp // 10
vm = vm // 10
removed += 1
return (vr + (1 if vr == vm or last_removed >= 5 else 0), e10 + removed)
## Ryu's f2s over the same tables: the shortest decimal digits * 10^exponent of a finite,
## nonzero f32.
func shortest32(ieee_mantissa: u32, ieee_exponent: u32) -> (u32, i32):
var e2: i32 = 0
var m2: u32 = 0
if ieee_exponent == 0:
e2 = 1 - 127 - 23 - 2
m2 = ieee_mantissa
else:
e2 = (i32)ieee_exponent - 127 - 23 - 2
m2 = ((u32)1 << 23) | ieee_mantissa
let accept_bounds = (m2 & 1) == 0
let mv = 4 * m2
let mp = 4 * m2 + 2
let mm_shift: u32 = 1 if ieee_mantissa != 0 or ieee_exponent <= 1 else 0
let mm = 4 * m2 - 1 - mm_shift
var vr: u32 = 0
var vp: u32 = 0
var vm: u32 = 0
var e10: i32 = 0
var vm_trailing_zeros = false
var vr_trailing_zeros = false
var last_removed: u32 = 0
if e2 >= 0:
let q = log10_pow2(e2)
e10 = q
let k = 61 + pow5_bits(q) - 1
let i = -e2 + q + k
vr = pow5_inv_div_pow2(mv, q, i)
vp = pow5_inv_div_pow2(mp, q, i)
vm = pow5_inv_div_pow2(mm, q, i)
if q != 0 and (vp - 1) // 10 <= vm // 10:
let l = 61 + pow5_bits(q - 1) - 1
last_removed = pow5_inv_div_pow2(mv, q - 1, -e2 + q - 1 + l) % 10
if q <= 9:
if mv % 5 == 0:
vr_trailing_zeros = pow5_factor((u64)mv) >= (u32)q
elif accept_bounds:
vm_trailing_zeros = pow5_factor((u64)mm) >= (u32)q
elif pow5_factor((u64)mp) >= (u32)q:
vp -= 1
else:
let q = log10_pow5(-e2)
e10 = q + e2
let i = -e2 - q
let k = pow5_bits(i) - 61
var j = q - k
vr = pow5_div_pow2(mv, i, j)
vp = pow5_div_pow2(mp, i, j)
vm = pow5_div_pow2(mm, i, j)
if q != 0 and (vp - 1) // 10 <= vm // 10:
j = q - 1 - (pow5_bits(i + 1) - 61)
last_removed = pow5_div_pow2(mv, i + 1, j) % 10
if q <= 1:
vr_trailing_zeros = true
if accept_bounds:
vm_trailing_zeros = mm_shift == 1
else:
vp -= 1
elif q < 31:
vr_trailing_zeros = (mv & (((u32)1 << (u32)(q - 1)) - 1)) == 0
let (digits, exponent) = trimmed((u64)vr, (u64)vp, (u64)vm, e10, accept_bounds, vm_trailing_zeros, vr_trailing_zeros, (u64)last_removed)
return (u32(digits), exponent)
## floor(log2(5^e)) + 1 for 0 <= e <= 3528.
inline func pow5_bits(e: i32) -> i32:
return (i32)((((u32)e) * 1217359) >> 19) + 1
## floor(log10(2^e)) for 0 <= e <= 1650.
inline func log10_pow2(e: i32) -> i32:
return (i32)((((u32)e) * 78913) >> 18)
## floor(log10(5^e)) for 0 <= e <= 2620.
inline func log10_pow5(e: i32) -> i32:
return (i32)((((u32)e) * 732923) >> 20)
## How many times 5 divides `value` (nonzero).
func pow5_factor(value: u64) -> u32:
var rest = value
var count: u32 = 0
while rest % 5 == 0:
rest = rest // 5
count += 1
return count
## (m * (high:low)) >> j for Ryu's 125-bit multipliers.
inline func mul_shift64(m: u64, low: u64, high: u64, j: i32) -> u64:
var b0_low: u64 = 0
let b0_high = product(m, low, &b0_low)
var b2_low: u64 = 0
var b2_high = product(m, high, &b2_low)
let sum_low = b2_low +% b0_high
if sum_low < b2_low:
b2_high += 1
let shift = (u64)(j - 64)
if shift == 0:
return sum_low
if shift >= 64:
return b2_high >> (shift - 64)
return (b2_high << (64 - shift)) | (sum_low >> shift)
inline func mul_shift32(m: u32, factor: u64, shift: i32) -> u32:
let low = (u64)m * (factor & 0xFFFFFFFF)
let high = (u64)m * (factor >> 32)
let sum = (low >> 32) + high
return (u32)(sum >> (u64)(shift - 32))
inline func pow5_inv_div_pow2(m: u32, q: i32, j: i32) -> u32:
return mul_shift32(m, pow5_inv_split[(usize)q * 2 + 1] + 1, j)
inline func pow5_div_pow2(m: u32, i: i32, j: i32) -> u32:
return mul_shift32(m, pow5_split[(usize)i * 2 + 1], j)
## The 128-bit product a * b: the high word, the low word stored in `low`. Ryu's
## multiplications and strings' float parsing (Lemire's) both take it.
pub inline func product(a: u64, b: u64, low: u64*) -> u64:
let a0 = a & 0xFFFFFFFF
let a1 = a >> 32
let b0 = b & 0xFFFFFFFF
let b1 = b >> 32
let p00 = a0 * b0
let p01 = a0 * b1
let p10 = a1 * b0
let p11 = a1 * b1
let middle = (p00 >> 32) + (p01 & 0xFFFFFFFF) + (p10 & 0xFFFFFFFF)
*low = (middle << 32) | (p00 & 0xFFFFFFFF)
return p11 + (p01 >> 32) + (p10 >> 32) + (middle >> 32)