use crate::el_table::EL_POWERS;
pub(crate) const POW10: [f64; 23] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16,
1e17, 1e18, 1e19, 1e20, 1e21, 1e22,
];
const SMALLEST_POWER_OF_TEN: i64 = -342;
const LARGEST_POWER_OF_TEN: i64 = 308;
const MANTISSA_EXPLICIT_BITS: i32 = 52;
const MINIMUM_EXPONENT: i32 = -1023;
const INFINITE_POWER: i32 = 0x7FF;
const MIN_EXPONENT_ROUND_TO_EVEN: i64 = -4;
const MAX_EXPONENT_ROUND_TO_EVEN: i64 = 23;
#[inline(always)]
fn power(q: i64) -> i32 {
(((152_170 + 65_536) * q) >> 16) as i32 + 63
}
#[inline]
pub(crate) fn eisel_lemire(w: u64, q: i64) -> Option<f64> {
debug_assert!(w != 0);
debug_assert!((SMALLEST_POWER_OF_TEN..=LARGEST_POWER_OF_TEN).contains(&q));
let lz = w.leading_zeros() as i32;
let w_norm = w << lz;
let idx = (q - SMALLEST_POWER_OF_TEN) as usize;
let (hi5, lo5) = EL_POWERS[idx];
let first = (w_norm as u128) * (hi5 as u128);
let mut product_hi = (first >> 64) as u64;
let mut product_lo = first as u64;
if product_hi & 0x1FF == 0x1FF {
let second = (w_norm as u128) * (lo5 as u128);
let second_hi = (second >> 64) as u64;
let (sum, carry) = product_lo.overflowing_add(second_hi);
product_lo = sum;
product_hi = product_hi.wrapping_add(carry as u64);
if product_hi & 0x1FF == 0x1FF && product_lo.wrapping_add(1) == 0 {
return None;
}
}
let upperbit = (product_hi >> 63) as i32;
let mut mantissa = product_hi >> (upperbit + 64 - MANTISSA_EXPLICIT_BITS - 3);
let mut power2 = power(q) + upperbit - lz - MINIMUM_EXPONENT;
if power2 <= 0 {
if -power2 + 1 >= 64 {
return Some(0.0);
}
mantissa >>= -power2 + 1;
mantissa += mantissa & 1;
mantissa >>= 1;
let exp_field = u64::from(mantissa >= (1 << MANTISSA_EXPLICIT_BITS));
return Some(f64::from_bits(
(exp_field << MANTISSA_EXPLICIT_BITS)
| (mantissa & ((1 << MANTISSA_EXPLICIT_BITS) - 1)),
));
}
if product_lo <= 1
&& (MIN_EXPONENT_ROUND_TO_EVEN..=MAX_EXPONENT_ROUND_TO_EVEN).contains(&q)
&& mantissa & 3 == 1
&& (mantissa << (upperbit + 64 - MANTISSA_EXPLICIT_BITS - 3)) == product_hi
{
mantissa &= !1u64;
}
mantissa += mantissa & 1;
mantissa >>= 1;
if mantissa >= (2 << MANTISSA_EXPLICIT_BITS) {
mantissa = 1 << MANTISSA_EXPLICIT_BITS;
power2 += 1;
}
mantissa &= !(1u64 << MANTISSA_EXPLICIT_BITS);
if power2 >= INFINITE_POWER {
return Some(f64::INFINITY);
}
Some(f64::from_bits(
((power2 as u64) << MANTISSA_EXPLICIT_BITS) | mantissa,
))
}
#[cfg(test)]
mod tests {
use super::*;
fn reference(w: u64, q: i64) -> f64 {
let s = format!("{w}e{q}");
fast_float2::parse::<f64, _>(s.as_bytes()).unwrap()
}
fn check(w: u64, q: i64) {
if w == 0 || !(SMALLEST_POWER_OF_TEN..=LARGEST_POWER_OF_TEN).contains(&q) {
return;
}
if let Some(got) = eisel_lemire(w, q) {
let want = reference(w, q);
assert_eq!(
got.to_bits(),
want.to_bits(),
"w={w} q={q}: el={got:e} ref={want:e}"
);
}
}
#[test]
fn known_hard_cases() {
check(22250738585072014, -324); check(22250738585072011, -324);
check(17976931348623157, 292); check(5, -324); check(9007199254740993, 0); check(9007199254740995, 0);
check(1, 308);
check(1, -307);
check(1, -342);
check(99999999999999999, -200);
check(65613616943359375, -15); check(123456789012345679, -20);
}
#[test]
fn differential_sweep() {
let mut s: u64 = 0x9E3779B97F4A7C15;
let mut rng = move || {
s ^= s << 13;
s ^= s >> 7;
s ^= s << 17;
s
};
for _ in 0..300_000 {
let w = rng() >> (rng() % 45); let q = (rng() % 640) as i64 - 330;
check(w, q);
}
}
#[test]
fn exponent_grid() {
for q in -342..=308 {
for w in [
1u64,
9,
10,
99,
12345,
10_000_000_000_000_000,
u64::MAX >> 11,
] {
check(w, q);
}
}
}
}