#![allow(dead_code)]
#![allow(unused_variables)]
use std::fmt;
use std::cmp::Ordering;
use std::ops::*;
use std::str::FromStr;
use gcd::Gcd;
use integer_sqrt::IntegerSquareRoot;
use super::{ParseRatioErr, RatioErrKind, r32};
#[allow(non_camel_case_types)]
#[derive(Clone, Copy, Eq, Default)]
pub struct r64(u64);
const SIGN_BIT: u64 = 0x8000_0000_0000_0000;
const SIZE_FIELD: u64 = SIGN_BIT - 1 << FRACTION_SIZE + 1 >> 1;
const FRACTION_FIELD: u64 = (1 << FRACTION_SIZE) - 1;
const FRACTION_SIZE: u64 = 57;
pub const NAN: r64 = r64(SIZE_FIELD);
pub const MAX: r64 = r64(FRACTION_FIELD);
pub const MIN: r64 = r64(SIGN_BIT | FRACTION_FIELD);
pub const MIN_POSITIVE: r64 = r64(FRACTION_SIZE << FRACTION_SIZE | FRACTION_FIELD);
impl r64 {
#[inline]
fn new(num: i64, den: u64) -> r64 {
let size = 64 - den.leading_zeros() - 1;
let denom_field = (1 << size) - 1;
r64(0).set_sign(num.is_negative())
.set_denom_size(size as u64)
.set_fraction(
((denom_field ^ FRACTION_FIELD) >> size & num.abs() as u64) << size |
den & denom_field
)
}
#[inline]
fn denom_size(self) -> u64 {
(self.0 & SIZE_FIELD) >> FRACTION_SIZE
}
#[inline]
pub fn numer(self) -> u64 {
if self.denom_size() == FRACTION_SIZE { 1 }
else { (self.0 & FRACTION_FIELD) >> self.denom_size() }
}
#[inline]
pub fn denom(self) -> u64 {
let denom_region = (1 << self.denom_size()) - 1;
1 << self.denom_size() | self.0 & denom_region
}
#[inline]
fn set_sign(self, sign: bool) -> r64 {
r64(self.0 & !SIGN_BIT | (sign as u64) << 63)
}
#[inline]
fn set_denom_size(self, size: u64) -> r64 {
r64(self.0 & !SIZE_FIELD | (size & 0x3f) << FRACTION_SIZE)
}
#[inline]
fn set_fraction(self, frac: u64) -> r64 {
r64(self.0 & !FRACTION_FIELD | frac & FRACTION_FIELD)
}
#[inline]
fn from_parts(sign: bool, numer: u64, denom: u64) -> r64 {
let size = 64 - denom.leading_zeros() - 1;
let denom_field = (1 << size) - 1;
r64(
if sign { SIGN_BIT } else { 0 } |
(size as u64) << FRACTION_SIZE |
((denom_field ^ FRACTION_FIELD) >> size & numer) << size |
denom & denom_field
)
}
#[inline]
fn is_sign_positive(self) -> bool {
self.0 & SIGN_BIT == 0
}
#[inline]
fn is_sign_negative(self) -> bool {
self.0 & SIGN_BIT != 0
}
pub fn floor(self) -> r64 {
if self.is_negative() {
if self.numer() % self.denom() == 0 {
self
}
else {
r64::from_parts(self.is_negative(), self.numer() / self.denom() + 1, 1)
}
}
else {
self.trunc()
}
}
pub fn ceil(self) -> r64 {
if self.is_negative() {
self.trunc()
}
else {
if self.numer() % self.denom() == 0 {
self
}
else {
r64::from_parts(self.is_negative(), self.numer() / self.denom() + 1, 1)
}
}
}
pub fn round(self) -> r64 {
if self.is_negative() {
(self - r64(1) / r64(2)).ceil()
}
else {
(self + r64(1) / r64(2)).floor()
}
}
#[inline]
pub fn trunc(self) -> r64 {
r64::from_parts(self.is_negative(), self.numer() / self.denom(), 1)
}
#[inline]
pub fn fract(self) -> r64 {
let d = self.denom();
r64::from_parts(self.is_negative(), self.numer() % d, d)
}
#[inline]
pub fn abs(self) -> r64 {
self.set_sign(false)
}
pub fn signum(self) -> r64 {
if self.numer() == 0 || self.is_nan() {
r64(0)
}
else {
r64(self.0 & SIGN_BIT | 1)
}
}
pub fn pow(self, p: i32) -> r64 {
let num = self.numer().pow(p.abs() as u32);
let den = self.denom().pow(p.abs() as u32);
if p >= 0 {
r64::from_parts(self.is_negative(), num, den)
}
else {
r64::from_parts(self.is_negative(), den, num)
}
}
pub fn checked_pow(self, p: i32) -> Option<r64> {
let num = self.numer().checked_pow(p.abs() as u32);
let den = self.denom().checked_pow(p.abs() as u32);
match (num, den) {
(Some(num), Some(den)) =>
Some(if p >= 0 {
r64::from_parts(self.is_negative(), num, den)
}
else {
r64::from_parts(self.is_negative(), den, num)
}),
_ => None
}
}
pub fn checked_sqrt(self) -> Option<r64> {
let nsqrt = self.numer().integer_sqrt();
let dsqrt = self.denom().integer_sqrt();
if self.numer() == nsqrt * nsqrt && self.denom() == dsqrt * dsqrt {
Some(r64::from_parts(self.is_negative(), nsqrt, dsqrt))
}
else {
None
}
}
#[doc(hidden)]
pub fn sqrt(self) -> r64 {
let f: f64 = self.into();
r64::from(f.sqrt())
}
#[inline]
pub fn is_nan(self) -> bool {
self.denom_size() > FRACTION_SIZE
}
#[inline]
pub fn is_normal(self) -> bool {
self.numer() != 0
&& !(self.numer() == 1 && self.denom() == FRACTION_SIZE)
&& !self.is_nan()
}
#[inline]
pub fn is_positive(self) -> bool {
self.numer() != 0 && self.is_sign_positive()
}
#[inline]
pub fn is_negative(self) -> bool {
self.numer() != 0 && self.is_sign_negative()
}
#[inline]
pub fn recip(self) -> r64 {
assert!(self.numer() != 0, "attempt to divide by zero");
assert!(self.denom_size() < FRACTION_SIZE, "subnormal overflow");
r64::from_parts(self.is_negative(), self.denom(), self.numer())
}
pub fn max(self, other: r64) -> r64 {
match (self.is_nan(), other.is_nan()) {
(true, true) => NAN,
(true, false) => self,
(false, true) => other,
(false, false) => match self.partial_cmp(&other).unwrap() {
Ordering::Less => other,
_ => self
}
}
}
pub fn min(self, other: r64) -> r64 {
match (self.is_nan(), other.is_nan()) {
(true, true) => NAN,
(true, false) => self,
(false, true) => other,
(false, false) => match self.partial_cmp(&other).unwrap() {
Ordering::Greater => other,
_ => self
}
}
}
#[inline]
pub fn to_bits(self) -> u64 { self.0 }
#[inline]
pub fn from_bits(bits: u64) -> r64 { r64(bits) }
pub fn simplify(self) -> r64 {
if self.is_nan() {
return self;
}
if self.numer() == 0 {
return r64(0);
}
let n = self.numer();
let d = self.denom();
let gcd = n.gcd(d);
r64::from_parts(self.is_negative(), n / gcd, d / gcd)
}
#[doc(hidden)]
pub fn checked_add(self, rhs: r64) -> Option<r64> {
unimplemented!()
}
#[doc(hidden)]
pub fn checked_sub(self, rhs: r64) -> Option<r64> {
unimplemented!()
}
#[doc(hidden)]
pub fn checked_mul(self, rhs: r64) -> Option<r64> {
unimplemented!()
}
#[doc(hidden)]
pub fn checked_div(self, rhs: r64) -> Option<r64> {
unimplemented!()
}
#[doc(hidden)]
pub fn checked_rem(self, rhs: r64) -> Option<r64> {
unimplemented!()
}
}
impl fmt::Display for r64 {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.is_nan() {
return f.write_str("NaN");
}
let norm = self.simplify();
if norm.is_negative() {
f.write_str("-")?;
}
write!(f, "{}", norm.numer())?;
if norm.denom_size() > 0 {
write!(f, "/{}", norm.denom())?;
}
Ok(())
}
}
impl fmt::Debug for r64 {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.is_nan() {
return f.write_str("NaN");
}
if self.is_sign_negative() {
f.write_str("-")?;
}
write!(f, "{}/{}", self.numer(), self.denom())
}
}
impl FromStr for r64 {
type Err = ParseRatioErr;
fn from_str(src: &str) -> Result<Self, Self::Err> {
if src.is_empty() {
return Err(ParseRatioErr { kind: RatioErrKind::Empty });
}
if src == "NaN" {
return Ok(NAN);
}
if let Some(pos) = src.find('/') {
if pos == src.len() - 1 {
return Err(ParseRatioErr { kind: RatioErrKind::Invalid });
}
let numerator: i64 = src[0..pos].parse()?;
let denominator: u64 = src[pos+1..].parse()?;
if denominator == 0 {
return Err(ParseRatioErr { kind: RatioErrKind::Invalid });
}
let sign = numerator < 0;
let denom_size = 64 - denominator.leading_zeros() - 1;
if numerator.abs() == 1 && denom_size as u64 == FRACTION_SIZE {
let denominator = denominator & FRACTION_FIELD;
return Ok(r64::from_parts(sign, 1, denominator));
}
let frac_size = denom_size + (64 - numerator.leading_zeros());
if frac_size as u64 > FRACTION_SIZE {
Err(ParseRatioErr { kind: RatioErrKind::Overflow })
}
else {
Ok(r64::from_parts(sign, numerator.abs() as u64, denominator))
}
}
else {
let numerator: i64 = src.parse()?;
let mag = numerator.checked_abs()
.ok_or(ParseRatioErr { kind: RatioErrKind::Overflow })?;
let frac_size = 64 - mag.leading_zeros();
if frac_size as u64 > FRACTION_SIZE {
return Err(ParseRatioErr { kind: RatioErrKind::Overflow });
}
Ok(r64::from_parts(numerator < 0, mag as u64, 1))
}
}
}
impl From<u8> for r64 {
#[inline]
fn from(v: u8) -> Self { r64(v as u64) }
}
impl From<i8> for r64 {
fn from(v: i8) -> Self {
let n = if v == i8::min_value() { 128 } else { v.abs() as u64 };
r64::from_parts(v.is_negative(), n, 1)
}
}
impl From<u16> for r64 {
#[inline]
fn from(v: u16) -> Self { r64(v as u64) }
}
impl From<i16> for r64 {
fn from(v: i16) -> Self {
let n = if v == i16::min_value() { 32768 } else { v.abs() as u64 };
r64::from_parts(v.is_negative(), n, 1)
}
}
impl From<u32> for r64 {
#[inline]
fn from(v: u32) -> Self { r64(v as u64) }
}
impl From<i32> for r64 {
fn from(v: i32) -> Self {
let n = if v == i32::min_value() { 4294967296 } else { v.abs() as u64 };
r64::from_parts(v.is_negative(), n, 1)
}
}
impl From<r32> for r64 {
fn from(v: r32) -> Self {
r64::from_parts(v.is_negative(), v.numer() as u64, v.denom() as u64)
}
}
impl From<f32> for r64 {
fn from(f: f32) -> Self {
r32::from(f).into()
}
}
impl From<f64> for r64 {
fn from(mut f: f64) -> Self {
let N = (1 << 29) - 1;
let is_lorge = f.abs() > 1.0;
let is_neg = f < 0.0;
if f.is_nan() || f.is_infinite() {
return NAN;
}
if is_lorge { f = f.recip(); }
if is_neg { f = f.abs(); }
let (mut a, mut b) = (0, 1);
let (mut c, mut d) = (1, 1);
let mut is_mediant = false;
while b <= N && d <= N {
let mediant = (a + c) as f64 / (b + d) as f64;
if f == mediant {
is_mediant = true;
break;
}
else if f > mediant {
a = a + c;
b = b + d;
}
else {
c = a + c;
d = b + d;
}
}
let result = if is_mediant {
if b + d <= N { (a + c, b + d) }
else if d > b { (c, d) }
else { (a, b) }
}
else {
if b > N { (c, d) }
else { (a, b) }
};
if is_lorge {
return r64::from_parts(is_neg, result.1, result.0);
}
else {
return r64::from_parts(is_neg, result.0, result.1);
}
}
}
impl Into<f32> for r64 {
fn into(self) -> f32 {
let s = if self.is_negative() { -1.0 } else { 1.0 };
s * self.numer() as f32 / self.denom() as f32
}
}
impl Into<f64> for r64 {
fn into(self) -> f64 {
let s = if self.is_negative() { -1.0 } else { 1.0 };
s * self.numer() as f64 / self.denom() as f64
}
}
impl Neg for r64 {
type Output = r64;
fn neg(self) -> Self::Output {
r64(self.0 ^ SIGN_BIT)
}
}
impl PartialEq for r64 {
fn eq(&self, other: &r64) -> bool {
self.is_nan() && other.is_nan()
|| self.numer() == 0 && other.numer() == 0
|| self.simplify().0 == other.simplify().0
}
}
impl PartialOrd for r64 {
fn partial_cmp(&self, other: &r64) -> Option<Ordering> {
if self.is_nan() && other.is_nan()
|| self.numer() == 0 && other.numer() == 0 {
return Some(Ordering::Equal);
}
if self.is_nan() || other.is_nan() {
return None;
}
self.is_sign_positive()
.partial_cmp(&other.is_sign_positive())
.map(|c| c.then(
(self.numer() as u128 * other.denom() as u128)
.cmp(&(self.denom() as u128 * other.numer() as u128))
))
}
}
impl Mul for r64 {
type Output = r64;
fn mul(self, other: r64) -> r64 {
let s = self.is_negative() != other.is_negative();
let mut n = self.numer() as u128 * other.numer() as u128;
let mut d = self.denom() as u128 * other.denom() as u128;
let gcd = n.gcd(d);
n /= gcd;
d /= gcd;
dbg!(d);
debug_assert!(
((128 - d.leading_zeros() - 1) + (128 - n.leading_zeros())) as u64 <= FRACTION_SIZE,
"attempt to multiply with overflow"
);
r64::from_parts(s, n as u64, d as u64)
}
}
impl Div for r64 {
type Output = r64;
fn div(self, other: r64) -> r64 {
self * other.recip()
}
}
impl Add for r64 {
type Output = r64;
fn add(self, other: r64) -> r64 {
let selfsign = (self.signum().0 as i64).signum();
let othersign = (other.signum().0 as i64).signum();
let num =
(self.numer() as i64 * selfsign) * other.denom() as i64
+ self.denom() as i64 * (other.numer() as i64 * othersign);
let mut den = self.denom() as u128 * other.denom() as u128;
let s = num.is_negative();
let mut num = num.abs() as u128;
let gcd = num.gcd(den);
num /= gcd;
den /= gcd;
dbg!(den);
debug_assert!(
((128 - den.leading_zeros() - 1) + (128 - num.leading_zeros())) as u64 <= FRACTION_SIZE,
"attempt to add with overflow"
);
r64::from_parts(s, num as u64, den as u64)
}
}
impl Sub for r64 {
type Output = r64;
fn sub(self, other: r64) -> r64 {
self + -other
}
}
impl Rem for r64 {
type Output = r64;
fn rem(self, other: r64) -> r64 {
let div = self / other;
((div - div.floor()) * other).set_sign(self.is_negative())
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn simplify() {
assert_eq!(r64::from_parts(false, 4, 2).simplify(), r64::from_parts(false, 2, 1));
assert_eq!(r64::from_parts(true, 4, 2).simplify(), r64::from_parts(true, 2, 1));
}
#[test]
fn neg() {
assert_eq!((-r64(0)).0, SIGN_BIT);
assert_eq!((-r64(SIGN_BIT)).0, 0);
}
#[test]
fn signum() {
assert_eq!(r64(0).signum(), r64(0));
assert_eq!(r64(SIGN_BIT).signum(), r64(0));
assert_eq!(r64(1).signum(), r64(1));
assert_eq!(r64(2).signum(), r64(1));
assert_eq!(r64::from_parts(true, 1, 1).signum(), r64::from_parts(true, 1, 1));
assert_eq!(r64::from_parts(true, 2, 1).signum(), r64::from_parts(true, 1, 1));
}
#[test]
fn pow() {
assert_eq!(r64(0).pow(0), r64(1));
assert_eq!(r64(1).pow(1), r64(1));
assert_eq!(r64(2).pow(3), r64(8));
assert_eq!(r64(2).pow(-3), r64::from_str("1/8").unwrap());
}
#[test]
fn checked_pow() {
assert_eq!(r64(0).checked_pow(0), Some(r64(1)));
assert_eq!(r64(1).checked_pow(1), Some(r64(1)));
assert_eq!(r64(2).checked_pow(3), Some(r64(8)));
assert_eq!(r64(2).checked_pow(-3), Some(r64::from_str("1/8").unwrap()));
assert_eq!(r64(3).checked_pow(60), None);
}
#[test]
fn checked_sqrt() {
assert_eq!(r64(0).checked_sqrt(), Some(r64(0)));
assert_eq!(r64(1).checked_sqrt(), Some(r64(1)));
assert_eq!(r64(2).checked_sqrt(), None);
assert_eq!(r64(4).checked_sqrt(), Some(r64(2)));
}
#[test]
fn floor() {
assert_eq!(r64::from_parts(false, 3, 2).floor(), r64(1));
assert_eq!(r64::from_parts(false, 2, 1).floor(), r64(2));
assert_eq!(r64::from_parts(true, 3, 2).floor(), r64::from(-2_i8));
assert_eq!(r64::from_parts(true, 2, 1).floor(), r64::from(-2_i8));
}
#[test]
fn ceil() {
assert_eq!(r64::from_parts(false, 3, 2).ceil(), r64(2));
assert_eq!(r64::from_parts(false, 2, 1).ceil(), r64(2));
assert_eq!(r64::from_parts(true, 3, 2).ceil(), r64::from(-1_i8));
assert_eq!(r64::from_parts(true, 2, 1).ceil(), r64::from(-2_i8));
}
#[test]
fn round() {
assert_eq!(r64(1).round(), r64(1));
assert_eq!((-r64(1)).round(), r64::from(-1_i8));
assert_eq!((r64(3) / r64(2)).round(), r64(2));
assert_eq!((-r64(3) / r64(2)).round(), r64::from(-2_i8));
}
#[test]
fn fract() {
assert_eq!(r64(5).fract(), r64(0));
assert_eq!(r64::from_parts(false, 3, 2).fract(), r64::from_parts(false, 1, 2));
assert_eq!(r64::from_parts(true, 3, 2).fract(), r64::from_parts(true, 1, 2));
}
#[test]
fn trunc() {
assert_eq!(r64(5).trunc(), r64(5));
assert_eq!(r64::from_parts(false, 1, 2).trunc(), r64(0));
assert_eq!(r64::from_parts(true, 1, 2).trunc(), r64(0));
assert_eq!(r64::from_parts(false, 3, 2).trunc(), r64(1));
assert_eq!(r64::from_parts(true, 3, 2).trunc(), r64::from(-1 as i8));
}
#[test]
fn recip() {
assert_eq!(r64(5).recip(), r64::from_parts(false, 1, 5));
assert_eq!(r64::from_parts(false, 5, 2).recip(), r64::from_parts(false, 2, 5));
assert_eq!(r64(1).recip(), r64(1));
}
#[test]
fn cmp() {
assert!(r64(0) == r64(0));
assert!(r64(0) == -r64(0));
assert!(r64(0) < r64(1));
assert!(r64(2) < r64(3));
assert!(r64(0) > -r64(1));
assert!(r64(2) > -r64(3));
}
#[test]
fn mul() {
assert_eq!(r64(0) * r64(0), r64(0));
assert_eq!(r64(0) * r64(1), r64(0));
assert_eq!(r64(1) * r64(0), r64(0));
assert_eq!(r64(1) * r64(1), r64(1));
assert_eq!(-r64(1) * r64(1), -r64(1));
assert_eq!(r64(1) * -r64(1), -r64(1));
assert_eq!(-r64(1) * -r64(1), r64(1));
assert_eq!(r64(1) * r64(2), r64(2));
assert_eq!(r64(2) * r64(2), r64(4));
assert_eq!(
r64::from_parts(false, 1, 2) * r64::from_parts(false, 1, 2),
r64::from_parts(false, 1, 4)
);
assert_eq!(
r64::from_parts(true, 1, 2) * r64::from_parts(false, 1, 2),
r64::from_parts(true, 1, 4)
);
assert_eq!(
r64::from_parts(false, 2, 3) * r64::from_parts(false, 2, 3),
r64::from_parts(false, 4, 9)
);
assert_eq!(
r64::from_parts(false, 3, 2) * r64::from_parts(false, 2, 3),
r64(1)
);
}
#[test] #[should_panic]
fn mul_invalid() {
let _ = r64(1 << FRACTION_SIZE - 1) * r64(1 << FRACTION_SIZE - 1);
}
#[test]
fn div() {
assert_eq!(r64(0) / r64(1), r64(0));
assert_eq!(r64(0) / r64(2), r64(0));
assert_eq!(r64(1) / r64(1), r64(1));
assert_eq!(-r64(1) / r64(1), -r64(1));
assert_eq!(r64(1) / -r64(1), -r64(1));
assert_eq!(-r64(1) / -r64(1), r64(1));
assert_eq!(r64(1) / r64(2), r64::from_parts(false, 1, 2));
assert_eq!(r64(2) / r64(1), r64(2));
assert_eq!(r64(2) / r64(2), r64(1));
}
#[test]
fn rem() {
assert_eq!(r64(5) % r64(2), r64(1));
assert_eq!(r64(6) % r64(2), r64(0));
assert_eq!(r64(8) % (r64(3) / r64(2)), r64(1) / r64(2));
assert_eq!(-r64(5) % r64(2), -r64(1));
assert_eq!(r64(5) % -r64(2), r64(1));
assert_eq!(-r64(5) % -r64(2), -r64(1));
}
#[test]
fn add() {
assert_eq!(r64(0) + r64(0), r64(0));
assert_eq!(-r64(0) + r64(0), r64(0));
assert_eq!(r64(1) + r64(1), r64(2));
assert_eq!(r64(1) + -r64(1), r64(0));
assert_eq!(-r64(1) + r64(1), r64(0));
assert_eq!(-r64(1) + -r64(1), -r64(2));
assert_eq!(r64(2) + r64(2), r64(4));
assert_eq!(
r64::from_parts(false, 1, 2) + r64::from_parts(false, 3, 4),
r64::from_parts(false, 5, 4)
);
assert_eq!(
r64::from_parts(false, 1, 2) + r64::from_parts(true, 3, 4),
r64::from_parts(true, 1, 4)
);
assert_eq!(
r64::from_parts(true, 1, 2) + r64::from_parts(false, 3, 4),
r64::from_parts(false, 1, 4)
);
}
#[test] #[should_panic]
fn add_invalid() {
let _ = r64(1 << FRACTION_SIZE - 1) + r64(1 << FRACTION_SIZE - 1);
}
#[test]
fn from_str() {
assert_eq!("0".parse::<r64>().unwrap(), r64(0));
assert_eq!("1".parse::<r64>().unwrap(), r64(1));
assert_eq!("+1".parse::<r64>().unwrap(), r64(1));
assert_eq!("-1".parse::<r64>().unwrap(), r64::from(-1 as i8));
assert_eq!("1/1".parse::<r64>().unwrap(), r64(1));
}
#[test]
fn debug() {
assert_eq!(format!("{:?}", r64::from_parts(true, 0, 1)), "-0/1");
assert_eq!(format!("{:?}", NAN), "NaN");
}
#[test]
fn display() {
assert_eq!(format!("{}", r64::from_parts(false, 0, 1)), "0");
assert_eq!(format!("{}", NAN), "NaN");
assert_eq!(format!("{}", r64::from_parts(true, 3, 2)), "-3/2");
}
}