dymokomi/luce-browser-foundation
Source of release 0.6.1
0.6.1 / src / ak / string_conversions_3.lucb
#==============================================================================================
#
# string_conversions_3 - convert_to_decimal_exponential_form: shortest decimal digits
#
# DESCRIPTION:
# Port of AK/StringConversions.cpp (lines 155-173). The C++ asks {fmt}'s Dragonbox for the
# shortest decimal significand and exponent that round-trips to the value (the closest
# such, trailing zeros removed). Dragonbox is replaced, not ported: the same digits come
# from Burger and Dybvig's free-format algorithm ("Printing Floating-Point Numbers Quickly
# and Accurately", 1996) over exact big integers, which yields the shortest correctly
# rounded digits with the same round-to-even interval; among the shortest, the closest,
# and on an exact tie the even one, as Dragonbox (fmt 12.1's to_decimal).
#
#==============================================================================================
# mark: Big integers ============================================================================
## The number of 32-bit limbs of a DecimalBignum: 1280 bits, enough for 2^1076 * 10^324.
let decimal_bignum_limbs: usize = 40
## An unsigned big integer, little-endian 32-bit limbs.
struct DecimalBignum:
var limbs: u32[40]
## A big integer of a u64.
func decimal_bignum_from_u64(value: u64) -> DecimalBignum:
var result = DecimalBignum()
result.limbs[0] = (u32)value
result.limbs[1] = (u32)(value >> 32)
return result
## `value <<= bits`.
func decimal_bignum_shift_left(value: DecimalBignum*, bits: usize):
let limb_shift = bits // 32
let bit_shift = (u32)(bits % 32)
var i = decimal_bignum_limbs
while i > 0:
i -= 1
var limb: u32 = 0
if i >= limb_shift:
limb = value.limbs[i - limb_shift] << bit_shift
if bit_shift != 0 and i >= limb_shift + 1:
limb |= value.limbs[i - limb_shift - 1] >> (32 - bit_shift)
value.limbs[i] = limb
## `value *= factor`.
func decimal_bignum_multiply_small(value: DecimalBignum*, factor: u32):
var carry: u64 = 0
for i in 0..<decimal_bignum_limbs:
let product = (u64)value.limbs[i] * (u64)factor + carry
value.limbs[i] = (u32)product
carry = product >> 32
assert(carry == 0, "DecimalBignum overflow")
## `value *= 10^exponent`.
func decimal_bignum_multiply_power_of_ten(value: DecimalBignum*, exponent: usize):
for _i in 0..<exponent:
decimal_bignum_multiply_small(value, 10)
## `a + b`.
func decimal_bignum_add(a: const DecimalBignum*, b: const DecimalBignum*) -> DecimalBignum:
var result = DecimalBignum()
var carry: u64 = 0
for i in 0..<decimal_bignum_limbs:
let sum = (u64)a.limbs[i] + (u64)b.limbs[i] + carry
result.limbs[i] = (u32)sum
carry = sum >> 32
assert(carry == 0, "DecimalBignum overflow")
return result
## `a <=> b`: negative, zero or positive.
func decimal_bignum_compare(a: const DecimalBignum*, b: const DecimalBignum*) -> i32:
var i = decimal_bignum_limbs
while i > 0:
i -= 1
if a.limbs[i] != b.limbs[i]:
return -1 if a.limbs[i] < b.limbs[i] else 1
return 0
## `a -= b` for a >= b.
func decimal_bignum_subtract(a: DecimalBignum*, b: const DecimalBignum*):
var borrow: u64 = 0
for i in 0..<decimal_bignum_limbs:
let subtrahend = (u64)b.limbs[i] + borrow
if (u64)a.limbs[i] >= subtrahend:
a.limbs[i] = (u32)((u64)a.limbs[i] - subtrahend)
borrow = 0
else:
a.limbs[i] = (u32)((u64)a.limbs[i] + 0x100000000 - subtrahend)
borrow = 1
assert(borrow == 0, "DecimalBignum underflow")
# mark: Shortest digits =========================================================================
## The shortest decimal form of `significand * 2^exponent` (a finite, non-zero binary float of
## `precision` significand bits whose smallest exponent is `minimum_exponent`).
func shortest_decimal_form(significand: u64, exponent: i32, precision: u32, minimum_exponent: i32, sign: bool) -> DecimalExponentialForm:
let hidden_bit = (u64)1 << (u64)(precision - 1)
# IEEE rounds to even, so the rounding interval includes its bounds for even significands.
let is_even = (significand & 1) == 0
var r = decimal_bignum_from_u64(significand)
var s = decimal_bignum_from_u64(1)
var m_plus = decimal_bignum_from_u64(1)
var m_minus = decimal_bignum_from_u64(1)
if exponent >= 0:
let shift = usize(exponent)
if significand != hidden_bit:
decimal_bignum_shift_left(&r, shift + 1)
s = decimal_bignum_from_u64(2)
decimal_bignum_shift_left(&m_plus, shift)
decimal_bignum_shift_left(&m_minus, shift)
else:
decimal_bignum_shift_left(&r, shift + 2)
s = decimal_bignum_from_u64(4)
decimal_bignum_shift_left(&m_plus, shift + 1)
decimal_bignum_shift_left(&m_minus, shift)
elif exponent == minimum_exponent or significand != hidden_bit:
decimal_bignum_shift_left(&r, 1)
decimal_bignum_shift_left(&s, usize(1 - exponent))
else:
decimal_bignum_shift_left(&r, 2)
decimal_bignum_shift_left(&s, usize(2 - exponent))
m_plus = decimal_bignum_from_u64(2)
# k estimates ceil(log10(value)), low by at most one.
var bit_length: i32 = 0
while bit_length < 64 and (significand >> (u64)bit_length) != 0:
bit_length += 1
let estimate = f64(exponent + bit_length - 1) * 0.30102999566398114 - 1e-10
var k = (i32)estimate
if f64(k) < estimate:
k += 1
if k >= 0:
decimal_bignum_multiply_power_of_ten(&s, usize(k))
else:
decimal_bignum_multiply_power_of_ten(&r, usize(-k))
decimal_bignum_multiply_power_of_ten(&m_plus, usize(-k))
decimal_bignum_multiply_power_of_ten(&m_minus, usize(-k))
# Fix the estimate: the upper bound must stay below 10^k.
var high = decimal_bignum_add(&r, &m_plus)
let too_low = decimal_bignum_compare(&high, &s)
if too_low > 0 or (is_even and too_low == 0):
k += 1
decimal_bignum_multiply_small(&s, 10)
var digits: u64 = 0
var digit_count: i32 = 0
while true:
decimal_bignum_multiply_small(&r, 10)
decimal_bignum_multiply_small(&m_plus, 10)
decimal_bignum_multiply_small(&m_minus, 10)
var digit: u64 = 0
while decimal_bignum_compare(&r, &s) >= 0:
decimal_bignum_subtract(&r, &s)
digit += 1
let low_comparison = decimal_bignum_compare(&r, &m_minus)
let termination_low = low_comparison < 0 or (is_even and low_comparison == 0)
high = decimal_bignum_add(&r, &m_plus)
let high_comparison = decimal_bignum_compare(&high, &s)
let termination_high = high_comparison > 0 or (is_even and high_comparison == 0)
digit_count += 1
if not termination_low and not termination_high:
digits = digits * 10 + digit
continue
if termination_low and not termination_high:
digits = digits * 10 + digit
elif not termination_low and termination_high:
digits = digits * 10 + digit + 1
else:
# Both neighbours round-trip: take the closer one, and on an exact tie the even one,
# as Dragonbox does (`y_mul.is_integer & (significand % 2 != 0)` in to_decimal,
# the `% 2` choice of shorter_interval_case).
var twice_r = r
decimal_bignum_multiply_small(&twice_r, 2)
let middle = decimal_bignum_compare(&twice_r, &s)
let round_down = middle < 0 or (middle == 0 and digit % 2 == 0)
digits = digits * 10 + (digit if round_down else digit + 1)
break
var decimal_exponent = k - digit_count
while digits % 10 == 0:
digits //= 10
decimal_exponent += 1
return DecimalExponentialForm(sign = sign, fraction = digits, exponent = decimal_exponent)
## Ported from AK/StringConversions.cpp:155 AK::convert_to_decimal_exponential_form<double>: the
## sign, shortest round-trip decimal significand and exponent of a finite double.
pub func convert_to_decimal_exponential_form_f64(value: f64) -> DecimalExponentialForm:
let bits = value.bits()
let sign = (bits >> 63) != 0
let biased_exponent = (i32)((bits >> 52) & 0x7ff)
let fraction = bits & 0xfffffffffffff
assert(biased_exponent != 0x7ff, "convert_to_decimal_exponential_form: infinity or NaN")
if biased_exponent == 0 and fraction == 0:
return DecimalExponentialForm(sign = sign, fraction = 0, exponent = 0)
if biased_exponent == 0:
return shortest_decimal_form(fraction, -1074, 53, -1074, sign)
return shortest_decimal_form(fraction | ((u64)1 << 52), biased_exponent - 1075, 53, -1074, sign)
## Ported from AK/StringConversions.cpp:155 AK::convert_to_decimal_exponential_form<float>.
pub func convert_to_decimal_exponential_form_f32(value: f32) -> DecimalExponentialForm:
let bits = value.bits()
let sign = (bits >> 31) != 0
let biased_exponent = (i32)((bits >> 23) & 0xff)
let fraction = (u64)(bits & 0x7fffff)
assert(biased_exponent != 0xff, "convert_to_decimal_exponential_form: infinity or NaN")
if biased_exponent == 0 and fraction == 0:
return DecimalExponentialForm(sign = sign, fraction = 0, exponent = 0)
if biased_exponent == 0:
return shortest_decimal_form(fraction, -149, 24, -149, sign)
return shortest_decimal_form(fraction | ((u64)1 << 23), biased_exponent - 150, 24, -149, sign)