use std::cmp::Ordering;
use std::sync::OnceLock;
use super::arith::{
D, DIGIT_POWER_10, GUARD_CARRY, POW10_U64, decimal_digits, div, mul, pow10,
remaining_decimal_digits, rescale, round,
};
pub(super) fn from_f64(x: f64) -> (bool, u128, i32) {
debug_assert!(x.is_finite() && x != 0.0);
let bits = x.to_bits();
let neg = bits >> 63 != 0;
let frac = bits & 0x000F_FFFF_FFFF_FFFF;
let exp = (bits >> 52) & 0x7FF;
let d = if exp == 0 {
f2dec(frac, -1074, neg)
} else {
let frac = frac | 0x0010_0000_0000_0000;
let pow = exp as i32 - 1075;
match pow.cmp(&0) {
Ordering::Equal => D::new(frac as u128, 0, neg),
Ordering::Less => {
let tz = frac.trailing_zeros().min((-pow) as u32);
f2dec(frac >> tz, pow + tz as i32, neg)
}
Ordering::Greater => f2dec(frac, pow, neg),
}
};
(neg, d.digits, d.exponent())
}
fn f2dec(mant: u64, b_exp: i32, neg: bool) -> D {
let d = D::new(mant as u128, 0, neg);
match b_exp.cmp(&0) {
Ordering::Equal => d,
Ordering::Less => round(div(d, power_of_two(-b_exp as u32))),
Ordering::Greater => round(mul(d, power_of_two(b_exp as u32))),
}
}
fn power_of_two(b: u32) -> D {
debug_assert!(b <= 1074);
if b < 128 {
return D::new(1u128 << b, 0, false);
}
let (digits, power, guard) = wide_powers_of_two()[(b - 128) as usize];
D {
digits,
scale: -(power as i16),
neg: false,
guard,
}
}
fn wide_powers_of_two() -> &'static [(u128, u16, u32)] {
static TABLE: OnceLock<Vec<(u128, u16, u32)>> = OnceLock::new();
TABLE.get_or_init(|| (128..=1074).map(truncated_power_of_two).collect())
}
fn truncated_power_of_two(b: u32) -> (u128, u16, u32) {
let mut n = vec![0u64; (b as usize + 24) / 64 + 1];
n[b as usize / 64] = 1u64 << (b % 64);
let mut carry = 0u128;
for limb in n.iter_mut() {
let v = *limb as u128 * GUARD_CARRY as u128 + carry;
*limb = v as u64;
carry = v >> 64;
}
debug_assert_eq!(carry, 0);
let digit_count = ((b as u64 * 78913) >> 18) as u32 + 1;
let mut power = digit_count - 39;
let (mut coefficient, mut guard) = split_guard(&div_pow10_big(&n, power));
if coefficient.1 != 0 {
power += 1;
(coefficient, guard) = split_guard(&div_pow10_big(&n, power));
}
debug_assert_eq!(coefficient.1, 0);
(coefficient.0, power as u16, guard)
}
fn split_guard(q: &[u64]) -> ((u128, u128), u32) {
debug_assert!(q.iter().skip(4).all(|&x| x == 0));
let w = |i: usize| q.get(i).copied().unwrap_or(0);
let mut out = [0u64; 4];
let mut rem: u128 = 0;
for i in (0..4).rev() {
let cur = (rem << 64) | w(i) as u128;
out[i] = (cur / GUARD_CARRY as u128) as u64;
rem = cur % GUARD_CARRY as u128;
}
(
(out[0] as u128 | ((out[1] as u128) << 64), out[2] as u128 | ((out[3] as u128) << 64)),
rem as u32,
)
}
fn div_pow10_big(n: &[u64], mut power: u32) -> Vec<u64> {
let mut q = n.to_vec();
while power > 0 {
let p = power.min(DIGIT_POWER_10);
let d = POW10_U64[p as usize] as u128;
let mut rem = 0u128;
for limb in q.iter_mut().rev() {
let cur = (rem << 64) | *limb as u128;
*limb = (cur / d) as u64;
rem = cur % d;
}
power -= p;
}
while q.len() > 1 && q.last() == Some(&0) {
q.pop();
}
q
}
const MIN_10_EXP_REAL: i32 = -342;
const INFINITE_POWER: i32 = 0x7FF;
const EXP_MIN: i32 = -1022;
const SIG_BITS: u32 = 52;
const MAX_POWER_OF_TWO: u32 = 127;
const MAX_POWER_OF_FIVE: u32 = 55;
pub(super) fn to_f64(negative: bool, coefficient: u128, exponent: i32) -> f64 {
let v = to_f64_abs(coefficient, exponent);
if negative {
-v
} else {
v
}
}
fn to_f64_abs(coefficient: u128, exponent: i32) -> f64 {
if coefficient == 0 {
return 0.0;
}
if let Ok(w) = u64::try_from(coefficient) {
return u64_to_f64(w, exponent);
}
let mut w = coefficient;
let mut exp = exponent;
let mut inexact = false;
while w > u64::MAX as u128 {
let p = (decimal_digits(w) - DIGIT_POWER_10).min(DIGIT_POWER_10);
let d = POW10_U64[p as usize] as u128;
inexact |= !w.is_multiple_of(d);
w /= d;
exp += p as i32;
}
let w = w as u64;
if exp < MIN_10_EXP_REAL {
return 0.0;
} else if exp > f64::MAX_10_EXP {
return f64::INFINITY;
}
if !inexact {
return u64_to_f64(w, exp);
}
if w < u64::MAX {
let lo = nearest(w, exp);
if lo == nearest(w + 1, exp) {
return lo;
}
}
slow_to_f64(D::new(coefficient, (-exponent) as i16, false))
}
fn u64_to_f64(w: u64, exp: i32) -> f64 {
if exp < MIN_10_EXP_REAL {
0.0
} else if exp > f64::MAX_10_EXP {
f64::INFINITY
} else {
nearest(w, exp)
}
}
fn nearest(w: u64, exp: i32) -> f64 {
use std::io::Write as _;
let mut buf = [0u8; 40];
let mut cursor = &mut buf[..];
let _ = write!(cursor, "{w}e{exp}");
let len = 40 - cursor.len();
std::str::from_utf8(&buf[..len]).ok().and_then(|s| s.parse().ok()).unwrap_or(f64::NAN)
}
fn slow_to_f64(mut d: D) -> f64 {
let mut exp2 = 0_i32;
loop {
let point = decimal_point(&d);
if point > INFINITE_POWER {
return f64::INFINITY;
} else if point < -INFINITE_POWER {
return 0.0;
}
if point <= 0 {
break;
}
div_power_of_two(&mut d, point as u32);
exp2 += point;
}
while lt_half(&d) {
let point = decimal_point(&d);
if point > INFINITE_POWER {
return f64::INFINITY;
} else if point < -INFINITE_POWER {
return 0.0;
}
let shift = if point == 0 {
1
} else {
(-point) as u32
};
mul_power_of_two(&mut d, shift);
exp2 -= shift as i32;
}
exp2 -= 1;
while EXP_MIN > exp2 {
div_power_of_two(&mut d, 1);
exp2 += 1;
}
if exp2 - EXP_MIN + 1 >= INFINITE_POWER {
return f64::INFINITY;
}
mul_power_of_two(&mut d, SIG_BITS + 1);
let mut mantissa = round_to_u64(d);
if mantissa >> (SIG_BITS + 1) != 0 {
mantissa >>= 1;
exp2 += 1;
if exp2 - EXP_MIN + 1 >= INFINITE_POWER {
return f64::INFINITY;
}
}
let mut power2 = exp2 - EXP_MIN + 1;
if mantissa < (1_u64 << SIG_BITS) {
power2 -= 1;
}
let mantissa = mantissa & ((1_u64 << SIG_BITS) - 1);
f64::from_bits(mantissa | ((power2 as u64) << SIG_BITS))
}
fn decimal_point(d: &D) -> i32 {
d.digits.checked_ilog10().unwrap_or(0) as i32 + 1 - d.scale as i32
}
fn mul_power_of_two(d: &mut D, mut power: u32) {
while power > 0 {
let shift = power.min(MAX_POWER_OF_TWO);
*d = mul(*d, D::new(1u128 << shift, 0, false));
power -= shift;
}
}
fn div_power_of_two(d: &mut D, mut power: u32) {
while power > 0 {
let shift = power.min(MAX_POWER_OF_FIVE);
*d = mul(*d, D::new(5u128.pow(shift), shift as i16, false));
power -= shift;
}
}
fn lt_half(d: &D) -> bool {
let power = decimal_digits(d.digits) as i32 - d.scale as i32;
if power != 0 {
return power < 0;
}
let mut r = *d;
if r.guard == 0 {
while r.digits != 0 && r.digits.is_multiple_of(10) {
r.digits /= 10;
r.scale -= 1;
}
}
let ord = match r.scale.cmp(&1) {
Ordering::Equal => r.digits.cmp(&5),
Ordering::Greater => {
let p = (r.scale - 1) as u32;
if p > remaining_decimal_digits(5) {
Ordering::Less
} else {
r.digits.cmp(&(5 * pow10(p)))
}
}
Ordering::Less => {
let p = (1 - r.scale) as u32;
if p > remaining_decimal_digits(r.digits) {
Ordering::Greater
} else {
(r.digits * pow10(p)).cmp(&5)
}
}
};
ord == Ordering::Less
}
fn round_to_u64(mut d: D) -> u64 {
round_half_even(&mut d);
rescale(&mut d, 0);
round_half_even(&mut d);
let power = decimal_digits(d.digits).saturating_sub(20);
if power > 0 {
let scale = d.scale - power as i16;
rescale(&mut d, scale);
}
if d.digits > u64::MAX as u128 {
let scale = d.scale - 1;
rescale(&mut d, scale);
}
round_half_even(&mut d);
if d.digits >= u64::MAX as u128 {
u64::MAX
} else {
d.digits as u64
}
}
fn round_half_even(d: &mut D) {
let digit = d.take_guard().first_digit();
if digit > 5 || (digit == 5 && d.digits & 1 == 1) {
if d.digits == u128::MAX {
d.digits /= 10;
d.scale -= 1;
}
d.digits += 1;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn wide_powers_of_two_are_truncations() {
for (i, &(digits, power, guard)) in wide_powers_of_two().iter().enumerate() {
let b = i as u32 + 128;
let dd = decimal_digits(digits);
assert!(dd == 39 || (dd == 38 && digits >= (u128::MAX - 9) / 10), "2^{b}: {dd} digits");
assert!(guard < GUARD_CARRY as u32, "2^{b}: guard {guard}");
let expected = ((b as f64) * std::f64::consts::LOG10_2).floor() as u32 + 1;
assert_eq!(dd + power as u32, expected, "2^{b}");
}
}
#[test]
fn small_powers_of_two_are_exact() {
assert_eq!(power_of_two(127).digits, 1u128 << 127);
assert_eq!(power_of_two(0).digits, 1);
}
}