use super::exp_table::{CENTRE, EXP};
const ONE: i128 = 1 << 112;
const LN2: i128 = 0xb17217f7d1cf79abc9e3b39803f3;
const TERMS: usize = 11;
const COEFFICIENTS: [i128; TERMS + 1] = {
let mut coefficients = [0; TERMS + 1];
let mut factorial: i128 = 1;
let mut k = 0;
while k <= TERMS {
if k > 0 {
factorial *= k as i128;
}
coefficients[k] = (2 * ONE + factorial) / (2 * factorial);
k += 1;
}
coefficients
};
fn multiply(a: i128, b: i128) -> i128 {
let (x, y) = (a.unsigned_abs(), b.unsigned_abs());
debug_assert!(x >> 113 == 0 && y >> 113 == 0);
let (xl, xh) = (u128::from(x as u64), x >> 64);
let (yl, yh) = (u128::from(y as u64), y >> 64);
let middle = xl * yh + xh * yl + ((xl * yl) >> 64);
let magnitude = ((xh * yh) << 16) + (middle >> 48);
if (a < 0) != (b < 0) {
-(magnitude as i128)
} else {
magnitude as i128
}
}
fn round_div(value: i128, divisor: i128) -> i128 {
let half = divisor / 2;
if value >= 0 {
(value + half) / divisor
} else {
-((-value + half) / divisor)
}
}
pub fn exp(bits: u128) -> Option<u128> {
let x = fixed_input(bits)?;
let n = round_div(x, LN2);
let r = x - n * LN2;
let j = round_div(r, 1 << 104);
let t = r - (j << 104);
let entry = *EXP.get(usize::try_from(CENTRE as i128 + j).ok()?)?;
let mut polynomial = COEFFICIENTS[TERMS];
for coefficient in COEFFICIENTS[..TERMS].iter().rev() {
polynomial = coefficient + multiply(t, polynomial);
}
let m = multiply(entry as i128, polynomial);
let error = n.abs() + 64;
let lower = scaled_binary80(m - error, n)?;
(scaled_binary80(m + error, n)? == lower).then_some(lower)
}
fn fixed_input(bits: u128) -> Option<i128> {
let significand = bits as u64;
let exponent = ((bits >> 64) & 0x7fff) as i32;
if bits >> 80 != 0 || significand >> 63 == 0 {
return None;
}
let shift = exponent - 16383 - 63 + 112;
if !(9..=62).contains(&shift) {
return None;
}
let magnitude = i128::from(significand) << shift;
Some(if bits >> 79 == 1 {
-magnitude
} else {
magnitude
})
}
fn scaled_binary80(value: i128, n: i128) -> Option<u128> {
let magnitude = u128::try_from(value).ok().filter(|&v| v != 0)?;
let top = 127 - magnitude.leading_zeros() as i128;
let shift = top - 63;
let mut significand = if shift <= 0 {
magnitude << -shift
} else {
let retained = magnitude >> shift;
let remainder = magnitude & ((1 << shift) - 1);
let half = 1 << (shift - 1);
retained + u128::from(remainder > half || (remainder == half && retained & 1 != 0))
};
let mut exponent = 16383 + top - 112 + n;
if significand == 1 << 64 {
significand >>= 1;
exponent += 1;
}
(1..=32766)
.contains(&exponent)
.then_some((exponent as u128) << 64 | significand)
}
#[cfg(test)]
mod tests {
use super::*;
use astro_float_num::{BigFloat, Consts, RoundingMode, Sign};
fn q112(value: &BigFloat) -> i128 {
let (words, _, sign, exponent, _) = value.as_raw_parts().unwrap();
assert_eq!(sign, Sign::Pos);
let shift = words.len() as i32 * 64 - exponent - 113;
assert!(shift > 0, "{shift}");
let word = |i: usize| u128::from(words.get(i).copied().unwrap_or(0));
let (at, bits) = (shift as usize / 64, shift as u32 % 64);
let low = word(at) | (word(at + 1) << 64);
let doubled = if bits == 0 {
low
} else {
(low >> bits) | (word(at + 2) << (128 - bits))
};
((doubled + 1) >> 1) as i128
}
#[test]
fn table_and_constants_are_nearest_to_independent_values() {
let mut constants = Consts::new().unwrap();
for (at, &entry) in EXP.iter().enumerate() {
let j = at as i64 - CENTRE as i64;
let exponent = BigFloat::from_i64(j, 64)
.div(&BigFloat::from_u16(256, 64), 256, RoundingMode::ToEven)
.exp(256, RoundingMode::ToEven, &mut constants);
assert_eq!(entry as i128, q112(&exponent), "entry {j}");
}
let ln2 = BigFloat::from_u8(2, 64).ln(256, RoundingMode::ToEven, &mut constants);
assert_eq!(LN2, q112(&ln2));
let mut factorial = 1u128;
for (k, &coefficient) in COEFFICIENTS.iter().enumerate() {
if k > 0 {
factorial *= k as u128;
}
let product = coefficient as u128 * factorial;
assert!(product.abs_diff(1 << 112) <= factorial / 2, "{k}");
}
}
#[test]
fn every_reduced_argument_stays_in_the_table_and_series_range() {
for x in [
ONE * 11356,
-ONE * 11356,
LN2 / 2,
-LN2 / 2,
LN2 / 2 + 1,
1 << 104,
] {
let n = round_div(x, LN2);
let r = x - n * LN2;
let j = round_div(r, 1 << 104);
assert!(j.abs() <= CENTRE as i128, "{x}");
assert!((r - (j << 104)).abs() <= 1 << 103, "{x}");
}
}
}