7
\$\begingroup\$

Inspired by another question here on Code Review, I decided to try implementing a Fraction type in Rust.

Requirements:

  1. Able to be added, subtracted, multiplied, divided
  2. Able to be compared (equality and ordering)
  3. Able to be converted to the floating point representation of the fraction
  4. When printed to screen, automatically simplify the fraction

I created methods for arithmetic, as well as implementing Eq, PartialEq, and PartialOrd. As far as I can tell, I can't implement Ord itself, as the f64 type cannot be fully ordered. In my implementation for fmt::Display, I simplify the fraction and remove any '1' denominators from the display.

Ideally I'd place this into a module for use in my other programs, but I haven't wrapped my head around the crate / module system yet.


#![crate_type = "lib"]

use std::fmt;
use std::cmp;

//////////
pub struct Fraction {
    numerator: i64,
    denominator: i64,
}

impl fmt::Display for Fraction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // Reduce, THEN write
        let temp: Fraction = self.reduce();
        if temp.denominator == 1 {
            write!(f, "{}", temp.numerator)
        }
        else {
            write!(f, "{}/{}", temp.numerator, temp.denominator)
        }
    }
}

impl cmp::PartialEq for Fraction {
    fn eq(&self, other: &Fraction) -> bool {
        // Simplify both before comparing
        let simp_self = self.reduce();
        let simp_other = other.reduce();
        simp_self.numerator == simp_other.numerator && simp_self.denominator == simp_other.denominator
    }
}
impl cmp::Eq for Fraction {}

impl cmp::PartialOrd for Fraction {
    fn partial_cmp(&self, other: &Fraction) -> Option<cmp::Ordering> {
        self.to_decimal().partial_cmp(&other.to_decimal())
    }
}

impl Fraction {
    /// Creates a new fraction with the given numerator and denominator
    /// Panics if given a denominator of 0
    pub fn new(numerator: i64, denominator: i64) -> Fraction {
        if denominator == 0 { panic!("Tried to create a fraction with a denominator of 0!") }
        if denominator < 0 {
            // If the denominator is negative, multiply both by -1
            Fraction { numerator: -numerator, denominator: -denominator }
        }
        else {
            Fraction { numerator: numerator, denominator: denominator }
        }

    }

    /// Returns a new Fraction equal to this Fraction plus another
    pub fn add<'a>(&self, other: &'a Fraction) -> Fraction {
        Fraction { numerator: (self.numerator * other.denominator + other.numerator * self.denominator), denominator: (self.denominator * other.denominator) }
    }

    /// Returns a new Fraction equal to this Fraction minus another
    pub fn subtract<'a>(&self, other: &'a Fraction) -> Fraction {
        Fraction { numerator: (self.numerator * other.denominator - other.numerator * self.denominator), denominator: (self.denominator * other.denominator) }
    }

    /// Returns a new Fraction equal to this Fraction multiplied by another
    pub fn multiply<'a>(&self, other: &'a Fraction) -> Fraction {
        Fraction { numerator: (self.numerator * other.numerator), denominator: (self.denominator * other.denominator) }
    }

    /// Returns a new Fraction equal to this Fraction divided by another
    pub fn divide<'a>(&self, other: &'a Fraction) -> Fraction {
        Fraction { numerator: (self.numerator * other.denominator), denominator: (self.denominator * other.numerator) }
    }

    /// Returns a new Fraction that is equal to this one, but simplified
    pub fn reduce(&self) -> Fraction {
        // Divide numerator and denominator by gcd [use absolute value because negatives]
        let _gcd = gcd(self.numerator.abs(), self.denominator.abs());
        Fraction { numerator: (self.numerator / _gcd) , denominator: (self.denominator / _gcd) }
    }

    /// Returns a decimal equivalent to this Fraction
    pub fn to_decimal(&self) -> f64 {
        self.numerator as f64/ self.denominator as f64
    }
}
//////////

// Calculate the greatest common denominator for two numbers
pub fn gcd(a: i64, b: i64) -> i64 {
    // Terminal cases
    if a == b { return a }
    if a == 0 { return b }
    if b == 0 { return a }

    if a % 2 == 0 {       // a is even
        if b % 2 != 0 {   // b is odd
            return gcd(a/2, b)
        }
        else {              // a and b are even
            return gcd(a/2, b/2) * 2
        }
    }

    // a is odd
    if b % 2 == 0 {       // b is even
        return gcd(a, b/2)
    }

    // Reduce larger argument
    if a > b { return gcd((a - b)/2, b) }

    return gcd((b - a)/2, a)
}

#[test]
fn ordering_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(3, 4);
    let c = Fraction::new(4, 3);
    let d = Fraction::new(-1, 2);
    assert!(a < b);
    assert!(a <= b);
    assert!(c > b);
    assert!(c >= a);
    assert!(d < a);
}

#[test]
fn equality_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(2, 4);
    let c = Fraction::new(5, 5);
    assert!(a == b);
    assert!(a != c);
}

#[test]
fn arithmetic_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(3, 4);
    assert!(a.add(&a) == Fraction::new(1, 1));
    assert!(a.subtract(&a) == Fraction::new(0, 5));
    assert!(a.multiply(&b) == Fraction::new(3, 8));
    assert!(a.divide(&b) == Fraction::new(4, 6));
}
\$\endgroup\$
4
\$\begingroup\$
  1. There's no need to specify the crate type. Cargo knows if it's a library or a binary.

  2. Combine imports at the same level using the use path::to::{a, b, c} syntax.

  3. There's no need to specify the type most times; let the compiler do type inference when it can (in Display::fmt).

  4. Rust style has the curly braces on the same line as the else. Instead of

    }
    else {
    

    Use

    } else {
    
  5. Almost always derive(Debug) on your types.

  6. I try to avoid panics as much as possible, so I'd probably return a Result from Fraction::new. Good to see you documented the panic though.

  7. When constructing a struct, if you repeat yourself (Thing { foo: foo, bar: bar }), that can be simplified to Thing { foo, bar }.

  8. Use the Enter key a bit more; spread your arithmetic constructors across a few lines to allow for readability. All the math intertwined makes it look complicated.

  9. Your inherent arithmetic functions don't need explicit lifetimes as you aren't using the lifetime on the output. Remove them and let lifetime elision take over.

  10. Can choose to use Self instead of Fraction inside the impl blocks if you'd like.

  11. Don't prefix a variable with an underscore. This indicates that a variable has to exist but is intentially not used. There's no issues with shadowing a function with a variable if you aren't going to call it again.

  12. Even better than the inherent arithmetic methods, you can implement the std::ops traits. This gives you the ability to use + - * and /,as well as allowing you to implement the operators for both owned and borrowed values.

  13. I'd use a match to tighten up the GCD even / odd logic and avoid so many returns.

  14. There's some comments that repeat what the code is doing, but don't explain the why. Can be removed or improved.

use std::{cmp, fmt};
use std::ops::{Add, Sub, Mul, Div};

#[derive(Debug)]
pub struct Fraction {
    numerator: i64,
    denominator: i64,
}

impl Fraction {
    /// Creates a new fraction with the given numerator and denominator
    /// Panics if given a denominator of 0
    pub fn new(numerator: i64, denominator: i64) -> Self {
        if denominator == 0 { panic!("Tried to create a fraction with a denominator of 0!") }
        if denominator < 0 {
            Self { numerator: -numerator, denominator: -denominator }
        } else {
            Self { numerator, denominator }
        }
    }

    /// Returns a new Fraction that is equal to this one, but simplified
    pub fn reduce(&self) -> Self {
        // Use absolute value because negatives
        let gcd = gcd(self.numerator.abs(), self.denominator.abs());
        Self {
            numerator: (self.numerator / gcd),
            denominator: (self.denominator / gcd),
        }
    }

    /// Returns a decimal equivalent to this Fraction
    pub fn to_decimal(&self) -> f64 {
        self.numerator as f64/ self.denominator as f64
    }
}

impl fmt::Display for Fraction {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        let temp = self.reduce();
        if temp.denominator == 1 {
            write!(f, "{}", temp.numerator)
        } else {
            write!(f, "{}/{}", temp.numerator, temp.denominator)
        }
    }
}

impl cmp::PartialEq for Fraction {
    fn eq(&self, other: &Fraction) -> bool {
        let simp_self = self.reduce();
        let simp_other = other.reduce();
        simp_self.numerator == simp_other.numerator &&
            simp_self.denominator == simp_other.denominator
    }
}

impl cmp::Eq for Fraction {}

impl cmp::PartialOrd for Fraction {
    fn partial_cmp(&self, other: &Fraction) -> Option<cmp::Ordering> {
        self.to_decimal().partial_cmp(&other.to_decimal())
    }
}

impl<'a> Add for &'a Fraction {
    type Output = Fraction;

    fn add(self, other: Self) -> Fraction {
        Fraction {
            numerator: (self.numerator * other.denominator + other.numerator * self.denominator),
            denominator: (self.denominator * other.denominator),
        }
    }
}

impl<'a> Sub for &'a Fraction {
    type Output = Fraction;

    fn sub(self, other: Self) -> Fraction {
        Fraction {
            numerator: (self.numerator * other.denominator - other.numerator * self.denominator),
            denominator: (self.denominator * other.denominator),
        }
    }
}

impl<'a> Mul for &'a Fraction {
    type Output = Fraction;

    fn mul(self, other: Self) -> Fraction {
        Fraction {
            numerator: (self.numerator * other.numerator),
            denominator: (self.denominator * other.denominator),
        }
    }
}

impl<'a> Div for &'a Fraction {
    type Output = Fraction;

    fn div(self, other: Self) -> Fraction {
        Fraction {
            numerator: (self.numerator * other.denominator),
            denominator: (self.denominator * other.numerator),
        }
    }
}

// Calculate the greatest common denominator for two numbers
pub fn gcd(a: i64, b: i64) -> i64 {
    // Terminal cases
    if a == b { return a }
    if a == 0 { return b }
    if b == 0 { return a }

    let a_is_even = a % 2 == 0;
    let b_is_even = b % 2 == 0;

    match (a_is_even, b_is_even) {
        (true, true) => gcd(a/2, b/2) * 2,
        (true, false) => gcd(a/2, b),
        (false, true) => gcd(a, b/2),
        (false, false) => {
            if a > b {
                gcd((a - b)/2, b)
            } else {
                gcd((b - a)/2, a)
            }
        }
    }
}

#[test]
fn ordering_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(3, 4);
    let c = Fraction::new(4, 3);
    let d = Fraction::new(-1, 2);
    assert!(a < b);
    assert!(a <= b);
    assert!(c > b);
    assert!(c >= a);
    assert!(d < a);
}

#[test]
fn equality_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(2, 4);
    let c = Fraction::new(5, 5);
    assert!(a == b);
    assert!(a != c);
}

#[test]
fn arithmetic_test() {
    let a = Fraction::new(1, 2);
    let b = Fraction::new(3, 4);
    assert!(&a + &a == Fraction::new(1, 1));
    assert!(&a - &a == Fraction::new(0, 5));
    assert!(&a * &b == Fraction::new(3, 8));
    assert!(&a / &b == Fraction::new(4, 6));
}

I can't implement Ord itself, as the f64 type cannot be fully ordered.

Floating point numbers cannot be ordered, it's true, but you only have a floating point number because you chose to implement it that way. Since you maintain your data as integral values, you could choose to convert both fractions to equivalent fractions with a common denominator and then compare the numerator directly.

\$\endgroup\$
  • \$\begingroup\$ Good call on the ops trait; I didn't know that existed. I thought about using a Result for new, but didn't want to have to unwrap to use it. I'll try out implementing Ord via numerator. Thanks! \$\endgroup\$ – Dan Ambrogio Jun 9 '17 at 21:07
1
\$\begingroup\$

Why is this "negation logic" in new:

    if denominator < 0 {
        // If the denominator is negative, multiply both by -1
        Fraction { numerator: -numerator, denominator: -denominator }
    }
    else {
        Fraction { numerator: numerator, denominator: denominator }
    }

The way you have it set up, it doesn't matter, if someone gives me a number like (-3)/(-4), my first thought is this can be reduced to 3/4.

I would probably call reduce in the new function, so any Fraction constructed is immediately reduced. You could get an integer overflow sooner if you don't reduce stuff immediately depending on how hairy the fractions get from repeated arithmetic. Possibly a good exercise is to write a test that illustrates this overflow issue.

\$\endgroup\$
  • 1
    \$\begingroup\$ I agree that the negation seems redundant, but I'm not sure that immediately reducing the number helps in the long run. You can always have a sequence of operations that will result in overflow, and it would be up to the user of the library to try to reduce the value periodically, the library to reduce on every operation (adding runtime overhead), or to communicate the overflow condition on any operation (adding programmer overhead). \$\endgroup\$ – Shepmaster Jun 8 '17 at 21:42
  • 1
    \$\begingroup\$ @Shepmaster Fair enough. I would say it is a tradeoff. To be fair, I did say "probably" haha. \$\endgroup\$ – Dair Jun 8 '17 at 21:43
  • 1
    \$\begingroup\$ An interesting option is to attempt reducing at some "load factor": such as when the numerator or denominator are greater than i64::MAX / 4. I'd have to benchmark it, but that's how hash maps work most of the time: reconfigure at some load factor for performance reasons. \$\endgroup\$ – CAD97 Jun 9 '17 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.