use std::cmp::Ordering;
use std::fmt::Write;
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) enum Int {
I(i128),
F(f64),
}
const SMALL: f64 = 8.507_059_173_023_462e37;
impl Int {
#[allow(clippy::cast_possible_truncation)] pub(crate) fn of_f64(v: f64) -> Self {
if v.abs() < SMALL {
Self::I(v as i128)
} else {
Self::F(v)
}
}
pub(crate) fn cmp(self, b: Self) -> Ordering {
match (self, b) {
(Self::I(a), Self::I(b)) => a.cmp(&b),
(Self::F(a), Self::F(b)) => a.partial_cmp(&b).unwrap_or(Ordering::Equal),
(Self::I(_), Self::F(f)) => {
if f > 0.0 {
Ordering::Less
} else {
Ordering::Greater
}
}
(Self::F(f), Self::I(_)) => {
if f > 0.0 {
Ordering::Greater
} else {
Ordering::Less
}
}
}
}
pub(crate) fn sub(self, b: Self) -> Option<i128> {
match (self, b) {
(Self::I(a), Self::I(b)) => a.checked_sub(b),
(Self::F(a), Self::F(b)) if a.total_cmp(&b).is_eq() => Some(0),
_ => None,
}
}
pub(crate) fn abs_diff(self, b: Self) -> Mag {
let (sa, ma) = self.parts();
let (sb, mb) = b.parts();
if sa == sb {
if ma.cmp(&mb) == Ordering::Less {
mb.sub(&ma)
} else {
ma.sub(&mb)
}
} else {
ma.add(&mb)
}
}
fn parts(self) -> (bool, Mag) {
match self {
Self::I(i) => (i < 0, Mag::from_u128(i.unsigned_abs())),
Self::F(f) => (f < 0.0, Mag::from_f64(f.abs())),
}
}
}
const LIMBS: usize = 34;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Mag {
limbs: [u64; LIMBS],
}
impl Mag {
const ZERO: Self = Self { limbs: [0; LIMBS] };
pub(crate) fn from_u128(v: u128) -> Self {
let mut m = Self::ZERO;
let [lo, hi, ..] = &mut m.limbs;
#[allow(clippy::cast_possible_truncation)] {
*lo = v as u64;
*hi = (v >> 64) as u64;
}
m
}
fn from_f64(v: f64) -> Self {
let bits = v.to_bits();
let exp = i32::try_from((bits >> 52) & 0x7FF).unwrap_or(0);
if exp < 1075 {
#[allow(clippy::cast_possible_truncation, clippy::cast_sign_loss)]
return Self::from_u128(u128::from(v as u64));
}
let mantissa = (bits & ((1 << 52) - 1)) | (1 << 52);
let shift = usize::try_from(exp - 1075).unwrap_or(0);
let mut m = Self::ZERO;
let (limb, bit) = (shift / 64, shift % 64);
let wide = u128::from(mantissa) << bit;
#[allow(clippy::cast_possible_truncation)] for (k, part) in [wide as u64, (wide >> 64) as u64].into_iter().enumerate() {
if let Some(slot) = m.limbs.get_mut(limb + k) {
*slot = part;
}
}
m
}
fn cmp(&self, b: &Self) -> Ordering {
self.limbs.iter().rev().cmp(b.limbs.iter().rev())
}
fn add(&self, b: &Self) -> Self {
let mut out = Self::ZERO;
let mut carry = 0_u128;
for ((o, x), y) in out.limbs.iter_mut().zip(&self.limbs).zip(&b.limbs) {
let s = u128::from(*x) + u128::from(*y) + carry;
#[allow(clippy::cast_possible_truncation)] {
*o = s as u64;
}
carry = s >> 64;
}
out
}
fn sub(&self, b: &Self) -> Self {
let mut out = Self::ZERO;
let mut borrow = false;
for ((o, x), y) in out.limbs.iter_mut().zip(&self.limbs).zip(&b.limbs) {
let (d, b1) = x.overflowing_sub(*y);
let (d, b2) = d.overflowing_sub(u64::from(borrow));
*o = d;
borrow = b1 || b2;
}
out
}
pub(crate) fn mul(&self, b: &Self) -> Self {
let mut out = Self::ZERO;
for (i, x) in self.limbs.iter().enumerate() {
if *x == 0 {
continue;
}
let mut carry = 0_u128;
for (j, y) in b.limbs.iter().enumerate() {
let Some(slot) = out.limbs.get_mut(i + j) else {
break;
};
let t = u128::from(*x) * u128::from(*y) + u128::from(*slot) + carry;
#[allow(clippy::cast_possible_truncation)] {
*slot = t as u64;
}
carry = t >> 64;
}
}
out
}
pub(crate) fn above(&self, v: u64) -> bool {
self.cmp(&Self::from_u128(u128::from(v))) == Ordering::Greater
}
pub(crate) fn decimal(&self) -> String {
const CHUNK: u64 = 10_000_000_000_000_000_000; let mut n = *self;
let mut store = [0_u64; LIMBS];
let mut count = 0;
loop {
let mut rem = 0_u128;
for limb in n.limbs.iter_mut().rev() {
let cur = (rem << 64) | u128::from(*limb);
#[allow(clippy::cast_possible_truncation)] {
*limb = (cur / u128::from(CHUNK)) as u64;
}
rem = cur % u128::from(CHUNK);
}
if let Some(slot) = store.get_mut(count) {
#[allow(clippy::cast_possible_truncation)] {
*slot = rem as u64;
}
count += 1;
}
if n == Self::ZERO {
break;
}
}
let mut s = String::new();
let parts = store.get(..count).unwrap_or_default();
for (k, part) in parts.iter().rev().enumerate() {
if k == 0 {
let _ = write!(s, "{part}");
} else {
let _ = write!(s, "{part:019}");
}
}
s
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn products_are_exact() {
let a = Int::of_f64(2f64.powi(121)).abs_diff(Int::I(0));
let b = Int::I(1).abs_diff(Int::I(0));
assert_eq!(a.mul(&b).decimal(), "2658455991569831745807614120560689152");
let max = Int::of_f64(f64::MAX).abs_diff(Int::of_f64(-f64::MAX));
let p = max.mul(&max);
assert_eq!(p.decimal().len(), 618);
assert!(p.decimal().starts_with("12926802428524400"));
assert_eq!(Int::I(-5).abs_diff(Int::I(7)).decimal(), "12");
assert_eq!(Mag::ZERO.decimal(), "0");
assert!(Int::I(178_956_971).abs_diff(Int::I(0)).above(178_956_970));
}
#[test]
fn ints_compare_and_subtract_as_python_s() {
let big = Int::of_f64(1e38);
assert_eq!(big, Int::F(1e38));
assert_eq!(Int::of_f64(-3.0), Int::I(-3));
assert_eq!(big.cmp(Int::I(i128::MAX)), Ordering::Greater);
assert_eq!(Int::of_f64(-1e38).cmp(Int::I(i128::MIN)), Ordering::Less);
assert_eq!(big.sub(big), Some(0));
assert_eq!(big.sub(Int::I(0)), None);
assert_eq!(Int::I(5).sub(Int::I(-2)), Some(7));
}
}