Fraction
TODO: description
Example
fn main() { use frac::*; let mut a = Frac::new(8374927, 2983178).simplify(); println!("{a}"); let b: i64 = 31; a += b; println!("{a}"); let af: f64 = a.into(); println!("{af:.5}"); let (l, r) = a.lower_den(100); println!("{l} <= {a} <= {r}"); let (lf, rf): (f64, f64) = (l.into(), r.into()); println!("{lf:.5} {rf:.5}"); } mod frac { /// Note: Basic arithmetics on the fraction types do not simplify the fraction to reduce calls of GCD. /// Simplifications should all be done manually. use std::{fmt::Display, ops::*}; /// Numerator type pub type I = i64; /// Denominator type pub type U = u64; /// Fraction type. #[derive(Clone, Copy, Debug)] pub struct Frac { /// Numerator pub num: I, /// Denominator pub den: U, } impl Frac { /// Simplifies the fraction to the minimum denomicator. pub fn simplify(self) -> Self { fn gcd(mut a: U, mut b: U) -> U { while b != 0 { (a, b) = (b, a % b); } a } let g = gcd(self.num.unsigned_abs(), self.den); Self { num: self.num / g as I, den: self.den / g, } } /// Returns a fraction from a given numerator and denominator pub fn new(num: I, den: I) -> Self { debug_assert_ne!(den, 0); if den < 0 { Self { num: -num, den: (-den) as U, } } else { Self { num, den: den as U } } } /// Returns a reciprocal of the fraction pub fn recip(self) -> Self { use std::cmp::Ordering::*; match self.num.cmp(&0) { Less => Self { num: -(self.den as I), den: (-self.num) as U, }, Equal => panic!("Reciprocal of zero"), Greater => Self { num: self.den as I, den: self.num as U, }, } } /// Returns a floor of the fraction in an integer form pub fn floor(self) -> I { let Self { num, den } = self; let den = den as I; num.div_euclid(den) } /// Returns a ceil of the fraction in an integer form pub fn ceil(self) -> I { let Self { num, den } = self; let den = den as I; (num + den - 1).div_euclid(den) } /// Returns a rounded fraction in an integer form pub fn round(self) -> I { let Self { num, den } = self; let den = den as I; (2 * num + den).div_euclid(2 * den) } /// Returns self - self.floor() pub fn fract(self) -> Self { self - self.floor() } /// Returns two closest fractions to `x` given a maximum possible value for denominators. /// If the fraction is equal to `x` when converted to f64, then the both bounds are equal. /// This behavior is subject to change for more accurate approximation. pub fn wrap(x: f64, max_den: U) -> (Self, Self) { let ipart = x.floor() as I; let d = x.fract(); if d == 0. { return (ipart.into(), ipart.into()); } let [(mut ln, mut ld), (mut rn, mut rd)]: [(U, U); 2] = [(0, 1), (1, 1)]; while (ln, ld) != (rn, rd) { let (pl, pr) = ((ln, ld), (rn, rd)); // Update l let k1 = (ld as f64 * d - ln as f64).div_euclid(rn as f64 - rd as f64 * d) as U; let k2 = (max_den - ld).div_euclid(rd); let k = k1.min(k2); ln += k * rn; ld += k * rd; // Update r let k1 = (rn as f64 - rd as f64 * d).div_euclid(ld as f64 * d - ln as f64) as U; let k2 = (max_den - rd).div_euclid(ld); let k = k1.min(k2); rn += k * ln; rd += k * ld; if pl == (ln, ld) && pr == (rn, rd) { break; } } let l = Self::new(ln as I, ld as I) + ipart; let r = Self::new(rn as I, rd as I) + ipart; if x == l.into() { (l, l) } else if x == r.into() { (r, r) } else { (l, r) } } /// Returns two fractions `(l, r)` where `l <= self`, `r >= self`, and `l`, `r` both being /// the closest to `self` given a maximum value of denominators. This function can be /// used for approximating the fraction when the numberator or denominator is getting too /// large, but you don't need an exact value of the fraction. pub fn lower_den(self, max_den: U) -> (Self, Self) { if self.den <= max_den { return (self, self); } let ipart = self.floor(); let Self { num: dn, den: dd } = self.fract(); let dn = dn as U; let [(mut ln, mut ld), (mut rn, mut rd)]: [(U, U); 2] = [(0, 1), (1, 1)]; while (ln, ld) != (rn, rd) { let (pl, pr) = ((ln, ld), (rn, rd)); // Update l let k1 = (ld * dn - ln * dd).div_euclid(rn * dd - rd * dn); let k2 = (max_den - ld).div_euclid(rd); let k = k1.min(k2); ln += k * rn; ld += k * rd; // Update r let k1 = (rn * dd - rd * dn).div_euclid(ld * dn - ln * dd); let k2 = (max_den - rd).div_euclid(ld); let k = k1.min(k2); rn += k * ln; rd += k * ld; if pl == (ln, ld) && pr == (rn, rd) { break; } } let l = Self::new(ln as I, ld as I) + ipart; let r = Self::new(rn as I, rd as I) + ipart; (l, r) } } impl Default for Frac { fn default() -> Self { Frac { num: 0, den: 1 } } } impl Display for Frac { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { write!(f, "{}/{}", self.num, self.den) } } impl From<I> for Frac { fn from(num: I) -> Self { Self { num, den: 1 } } } impl From<Frac> for f64 { fn from(value: Frac) -> Self { value.num as f64 / value.den as f64 } } impl Neg for Frac { type Output = Self; fn neg(self) -> Self::Output { Self { num: -self.num, den: self.den, } } } impl Add for Frac { type Output = Self; fn add(self, rhs: Self) -> Self::Output { Self { num: self.num * rhs.den as I + self.den as I * rhs.num, den: self.den * rhs.den, } } } impl Sub for Frac { type Output = Self; fn sub(self, rhs: Self) -> Self::Output { Self { num: self.num * rhs.den as I - self.den as I * rhs.num, den: self.den * rhs.den, } } } impl Mul for Frac { type Output = Self; fn mul(self, rhs: Self) -> Self::Output { Self { num: self.num * rhs.num, den: self.den * rhs.den, } } } impl Div for Frac { type Output = Self; fn div(self, rhs: Self) -> Self::Output { self * rhs.recip() } } impl Add<I> for Frac { type Output = Self; fn add(self, rhs: I) -> Self::Output { let rhs: Frac = rhs.into(); self + rhs } } impl Sub<I> for Frac { type Output = Self; fn sub(self, rhs: I) -> Self::Output { let rhs: Frac = rhs.into(); self - rhs } } impl Mul<I> for Frac { type Output = Self; fn mul(self, rhs: I) -> Self::Output { let rhs: Frac = rhs.into(); self * rhs } } impl Div<I> for Frac { type Output = Self; fn div(self, rhs: I) -> Self::Output { let rhs: Frac = rhs.into(); self / rhs } } impl Add<Frac> for I { type Output = Frac; fn add(self, rhs: Frac) -> Self::Output { rhs + self } } impl Sub<Frac> for I { type Output = Frac; fn sub(self, rhs: Frac) -> Self::Output { -rhs + self } } impl Mul<Frac> for I { type Output = Frac; fn mul(self, rhs: Frac) -> Self::Output { rhs * self } } impl Div<Frac> for I { type Output = Frac; fn div(self, rhs: Frac) -> Self::Output { let lhs: Frac = self.into(); lhs / rhs } } impl AddAssign for Frac { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl SubAssign for Frac { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl MulAssign for Frac { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl DivAssign for Frac { fn div_assign(&mut self, rhs: Self) { *self = *self / rhs; } } impl AddAssign<I> for Frac { fn add_assign(&mut self, rhs: I) { *self = *self + rhs; } } impl SubAssign<I> for Frac { fn sub_assign(&mut self, rhs: I) { *self = *self - rhs; } } impl MulAssign<I> for Frac { fn mul_assign(&mut self, rhs: I) { *self = *self * rhs; } } impl DivAssign<I> for Frac { fn div_assign(&mut self, rhs: I) { *self = *self / rhs; } } impl PartialEq for Frac { fn eq(&self, rhs: &Self) -> bool { (self.num * rhs.den as I).eq(&(rhs.num * self.den as I)) } } impl Eq for Frac {} impl PartialOrd for Frac { fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> { (self.num * rhs.den as I).partial_cmp(&(rhs.num * self.den as I)) } } impl Ord for Frac { fn cmp(&self, rhs: &Self) -> std::cmp::Ordering { (self.num * rhs.den as I).cmp(&(rhs.num * self.den as I)) } } impl PartialEq<I> for Frac { fn eq(&self, rhs: &I) -> bool { let rhs: Frac = (*rhs).into(); self.eq(&rhs) } } impl PartialOrd<I> for Frac { fn partial_cmp(&self, rhs: &I) -> Option<std::cmp::Ordering> { let rhs: Frac = (*rhs).into(); self.partial_cmp(&rhs) } } impl PartialEq<Frac> for I { fn eq(&self, rhs: &Frac) -> bool { let lhs: Frac = (*self).into(); lhs.eq(rhs) } } impl PartialOrd<Frac> for I { fn partial_cmp(&self, rhs: &Frac) -> Option<std::cmp::Ordering> { let lhs: Frac = (*self).into(); lhs.partial_cmp(rhs) } } }
Code
mod frac {
/// Note: Basic arithmetics on the fraction types do not simplify the fraction to reduce calls of GCD.
/// Simplifications should all be done manually.
use std::{fmt::Display, ops::*};
/// Numerator type
pub type I = i64;
/// Denominator type
pub type U = u64;
/// Fraction type.
#[derive(Clone, Copy, Debug)]
pub struct Frac {
/// Numerator
pub num: I,
/// Denominator
pub den: U,
}
impl Frac {
/// Simplifies the fraction to the minimum denomicator.
pub fn simplify(self) -> Self {
fn gcd(mut a: U, mut b: U) -> U {
while b != 0 {
(a, b) = (b, a % b);
}
a
}
let g = gcd(self.num.unsigned_abs(), self.den);
Self {
num: self.num / g as I,
den: self.den / g,
}
}
/// Returns a fraction from a given numerator and denominator
pub fn new(num: I, den: I) -> Self {
debug_assert_ne!(den, 0);
if den < 0 {
Self {
num: -num,
den: (-den) as U,
}
} else {
Self { num, den: den as U }
}
}
/// Returns a reciprocal of the fraction
pub fn recip(self) -> Self {
use std::cmp::Ordering::*;
match self.num.cmp(&0) {
Less => Self {
num: -(self.den as I),
den: (-self.num) as U,
},
Equal => panic!("Reciprocal of zero"),
Greater => Self {
num: self.den as I,
den: self.num as U,
},
}
}
/// Returns a floor of the fraction in an integer form
pub fn floor(self) -> I {
let Self { num, den } = self;
let den = den as I;
num.div_euclid(den)
}
/// Returns a ceil of the fraction in an integer form
pub fn ceil(self) -> I {
let Self { num, den } = self;
let den = den as I;
(num + den - 1).div_euclid(den)
}
/// Returns a rounded fraction in an integer form
pub fn round(self) -> I {
let Self { num, den } = self;
let den = den as I;
(2 * num + den).div_euclid(2 * den)
}
/// Returns self - self.floor()
pub fn fract(self) -> Self {
self - self.floor()
}
/// Returns two closest fractions to `x` given a maximum possible value for denominators.
/// If the fraction is equal to `x` when converted to f64, then the both bounds are equal.
/// This behavior is subject to change for more accurate approximation.
pub fn wrap(x: f64, max_den: U) -> (Self, Self) {
let ipart = x.floor() as I;
let d = x.fract();
if d == 0. {
return (ipart.into(), ipart.into());
}
let [(mut ln, mut ld), (mut rn, mut rd)]: [(U, U); 2] = [(0, 1), (1, 1)];
while (ln, ld) != (rn, rd) {
let (pl, pr) = ((ln, ld), (rn, rd));
// Update l
let k1 = (ld as f64 * d - ln as f64).div_euclid(rn as f64 - rd as f64 * d) as U;
let k2 = (max_den - ld).div_euclid(rd);
let k = k1.min(k2);
ln += k * rn;
ld += k * rd;
// Update r
let k1 = (rn as f64 - rd as f64 * d).div_euclid(ld as f64 * d - ln as f64) as U;
let k2 = (max_den - rd).div_euclid(ld);
let k = k1.min(k2);
rn += k * ln;
rd += k * ld;
if pl == (ln, ld) && pr == (rn, rd) {
break;
}
}
let l = Self::new(ln as I, ld as I) + ipart;
let r = Self::new(rn as I, rd as I) + ipart;
if x == l.into() {
(l, l)
} else if x == r.into() {
(r, r)
} else {
(l, r)
}
}
/// Returns two fractions `(l, r)` where `l <= self`, `r >= self`, and `l`, `r` both being
/// the closest to `self` given a maximum value of denominators. This function can be
/// used for approximating the fraction when the numberator or denominator is getting too
/// large, but you don't need an exact value of the fraction.
pub fn lower_den(self, max_den: U) -> (Self, Self) {
if self.den <= max_den {
return (self, self);
}
let ipart = self.floor();
let Self { num: dn, den: dd } = self.fract();
let dn = dn as U;
let [(mut ln, mut ld), (mut rn, mut rd)]: [(U, U); 2] = [(0, 1), (1, 1)];
while (ln, ld) != (rn, rd) {
let (pl, pr) = ((ln, ld), (rn, rd));
// Update l
let k1 = (ld * dn - ln * dd).div_euclid(rn * dd - rd * dn);
let k2 = (max_den - ld).div_euclid(rd);
let k = k1.min(k2);
ln += k * rn;
ld += k * rd;
// Update r
let k1 = (rn * dd - rd * dn).div_euclid(ld * dn - ln * dd);
let k2 = (max_den - rd).div_euclid(ld);
let k = k1.min(k2);
rn += k * ln;
rd += k * ld;
if pl == (ln, ld) && pr == (rn, rd) {
break;
}
}
let l = Self::new(ln as I, ld as I) + ipart;
let r = Self::new(rn as I, rd as I) + ipart;
(l, r)
}
}
impl Default for Frac {
fn default() -> Self {
Frac { num: 0, den: 1 }
}
}
impl Display for Frac {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
write!(f, "{}/{}", self.num, self.den)
}
}
impl From<I> for Frac {
fn from(num: I) -> Self {
Self { num, den: 1 }
}
}
impl From<Frac> for f64 {
fn from(value: Frac) -> Self {
value.num as f64 / value.den as f64
}
}
impl Neg for Frac {
type Output = Self;
fn neg(self) -> Self::Output {
Self {
num: -self.num,
den: self.den,
}
}
}
impl Add for Frac {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self {
num: self.num * rhs.den as I + self.den as I * rhs.num,
den: self.den * rhs.den,
}
}
}
impl Sub for Frac {
type Output = Self;
fn sub(self, rhs: Self) -> Self::Output {
Self {
num: self.num * rhs.den as I - self.den as I * rhs.num,
den: self.den * rhs.den,
}
}
}
impl Mul for Frac {
type Output = Self;
fn mul(self, rhs: Self) -> Self::Output {
Self {
num: self.num * rhs.num,
den: self.den * rhs.den,
}
}
}
impl Div for Frac {
type Output = Self;
fn div(self, rhs: Self) -> Self::Output {
self * rhs.recip()
}
}
impl Add<I> for Frac {
type Output = Self;
fn add(self, rhs: I) -> Self::Output {
let rhs: Frac = rhs.into();
self + rhs
}
}
impl Sub<I> for Frac {
type Output = Self;
fn sub(self, rhs: I) -> Self::Output {
let rhs: Frac = rhs.into();
self - rhs
}
}
impl Mul<I> for Frac {
type Output = Self;
fn mul(self, rhs: I) -> Self::Output {
let rhs: Frac = rhs.into();
self * rhs
}
}
impl Div<I> for Frac {
type Output = Self;
fn div(self, rhs: I) -> Self::Output {
let rhs: Frac = rhs.into();
self / rhs
}
}
impl Add<Frac> for I {
type Output = Frac;
fn add(self, rhs: Frac) -> Self::Output {
rhs + self
}
}
impl Sub<Frac> for I {
type Output = Frac;
fn sub(self, rhs: Frac) -> Self::Output {
-rhs + self
}
}
impl Mul<Frac> for I {
type Output = Frac;
fn mul(self, rhs: Frac) -> Self::Output {
rhs * self
}
}
impl Div<Frac> for I {
type Output = Frac;
fn div(self, rhs: Frac) -> Self::Output {
let lhs: Frac = self.into();
lhs / rhs
}
}
impl AddAssign for Frac {
fn add_assign(&mut self, rhs: Self) {
*self = *self + rhs;
}
}
impl SubAssign for Frac {
fn sub_assign(&mut self, rhs: Self) {
*self = *self - rhs;
}
}
impl MulAssign for Frac {
fn mul_assign(&mut self, rhs: Self) {
*self = *self * rhs;
}
}
impl DivAssign for Frac {
fn div_assign(&mut self, rhs: Self) {
*self = *self / rhs;
}
}
impl AddAssign<I> for Frac {
fn add_assign(&mut self, rhs: I) {
*self = *self + rhs;
}
}
impl SubAssign<I> for Frac {
fn sub_assign(&mut self, rhs: I) {
*self = *self - rhs;
}
}
impl MulAssign<I> for Frac {
fn mul_assign(&mut self, rhs: I) {
*self = *self * rhs;
}
}
impl DivAssign<I> for Frac {
fn div_assign(&mut self, rhs: I) {
*self = *self / rhs;
}
}
impl PartialEq for Frac {
fn eq(&self, rhs: &Self) -> bool {
(self.num * rhs.den as I).eq(&(rhs.num * self.den as I))
}
}
impl Eq for Frac {}
impl PartialOrd for Frac {
fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
(self.num * rhs.den as I).partial_cmp(&(rhs.num * self.den as I))
}
}
impl Ord for Frac {
fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
(self.num * rhs.den as I).cmp(&(rhs.num * self.den as I))
}
}
impl PartialEq<I> for Frac {
fn eq(&self, rhs: &I) -> bool {
let rhs: Frac = (*rhs).into();
self.eq(&rhs)
}
}
impl PartialOrd<I> for Frac {
fn partial_cmp(&self, rhs: &I) -> Option<std::cmp::Ordering> {
let rhs: Frac = (*rhs).into();
self.partial_cmp(&rhs)
}
}
impl PartialEq<Frac> for I {
fn eq(&self, rhs: &Frac) -> bool {
let lhs: Frac = (*self).into();
lhs.eq(rhs)
}
}
impl PartialOrd<Frac> for I {
fn partial_cmp(&self, rhs: &Frac) -> Option<std::cmp::Ordering> {
let lhs: Frac = (*self).into();
lhs.partial_cmp(rhs)
}
}
}