Skip to content

Rational Numbers

Implement rational numbers: the four arithmetic operations, absolute value, integer powers, a real number raised to a rational power, and reduction to lowest terms.

Adapted from Exercism’s problem specification (MIT). Listed under Numbers & Math.

// FILE: rational_numbers.nomi
//# Rational numbers and their arithmetic.

/// A fraction kept in lowest terms with a positive denominator, so two
/// equal rationals have the same fields and `==` compares them.
pub opaque struct Rational
    numerator:   Int
    denominator: PositiveInt
end

/// A Rational other than zero: what `/` divides by.
pub subtype NonZeroRational Rational when fn r -> r.numerator != 0

impl Rational
    /// `numerator / denominator` in lowest terms. The denominator is not
    /// zero, so the reduction's divisor is not either.
    pub fn new(numerator: Int, denominator: NonZeroInt) -> Rational
        // The gcd of a number and a non-zero one is at least 1.
        gcd = PositiveInt.try_from(Int.gcd(numerator, denominator))!
        common = if denominator < 0 then -gcd else gcd
        // `denominator / common` has the sign of `denominator * common`.
        {numerator: numerator / common, denominator: PositiveInt.try_from(denominator / common)!}
    end

    pub fn numerator(r: Rational) -> Int
        r.numerator
    end

    pub fn denominator(r: Rational) -> Int
        r.denominator
    end

    pub fn abs(r: Rational) -> Rational
        {..r, numerator: Int.abs(..)}
    end

    /// `r` to the power `exponent`. A negative exponent raises the
    /// reciprocal, which zero has none of, so zero to a negative power
    /// traps.
    pub fn pow(r: Rational, exponent: Int) -> Rational
        case NonNegativeInt.try_from(exponent)
            Some(e) ->
                Rational.new(Int.pow(r.numerator, e), Int.pow(r.denominator, e))

            None ->
                e = NonNegativeInt.try_from(-exponent)!

                Rational.new(
                    Int.pow(r.denominator, e),
                    NonZeroInt.try_from(Int.pow(r.numerator, e))!,
                )
        end
    end

    /// `base` to the power `r`: the `r.denominator`th root of `base` to the
    /// power `r.numerator`.
    pub fn raise(base: Float, r: Rational) -> Float
        Float.pow(base, Int.to_float(r.numerator) / Int.to_float(r.denominator))
    end
end

impl Add<Rational, Rational> for Rational
    fn add(lhs: Rational, rhs: Rational) -> Rational
        Rational.new(
            lhs.numerator * rhs.denominator + rhs.numerator * lhs.denominator,
            lhs.denominator * rhs.denominator,
        )
    end
end

impl Subtract<Rational, Rational> for Rational
    fn subtract(lhs: Rational, rhs: Rational) -> Rational
        Rational.new(
            lhs.numerator * rhs.denominator - rhs.numerator * lhs.denominator,
            lhs.denominator * rhs.denominator,
        )
    end
end

impl Multiply<Rational, Rational> for Rational
    fn multiply(lhs: Rational, rhs: Rational) -> Rational
        Rational.new(lhs.numerator * rhs.numerator, lhs.denominator * rhs.denominator)
    end
end

impl Divide<NonZeroRational, Rational> for Rational
    /// The divisor is not zero, as `/` on `Int` takes a `NonZeroInt`.
    fn divide(lhs: Rational, rhs: NonZeroRational) -> Rational
        NonZeroRational(r) = rhs
        // A NonZeroRational's numerator is not zero.
        divisor = NonZeroInt.try_from(r.numerator)!
        Rational.new(lhs.numerator * r.denominator, lhs.denominator * divisor)
    end
end

// FILE: rational_numbers_test.nomi
import rational_numbers.{NonZeroRational, Rational}

/// The rational a canonical `[numerator, denominator]` pair writes.
fn rational((numerator, denominator): (Int, Int)) -> Rational
    Rational.new(numerator, NonZeroInt.try_from(denominator)!)
end

test "addition"
    [
        ("Add two positive rational numbers", (1, 2), (2, 3), (7, 6)),
        (
            "Add a positive rational number and a negative rational number",
            (1, 2),
            (-2, 3),
            (-1, 6),
        ),
        ("Add two negative rational numbers",             (-1, 2), (-2, 3), (-7, 6)),
        ("Add a rational number to its additive inverse", (1, 2),  (-1, 2), (0, 1)),
    ]
    |> subtests (description, a, b, expected), description
        assert rational(a) + rational(b) == rational(expected)
    end
end

test "subtraction"
    [
        ("Subtract two positive rational numbers", (1, 2), (2, 3), (-1, 6)),
        (
            "Subtract a positive rational number and a negative rational number",
            (1, 2),
            (-2, 3),
            (7, 6),
        ),
        ("Subtract two negative rational numbers", (-1, 2), (-2, 3), (1, 6)),
        ("Subtract a rational number from itself", (1, 2),  (1, 2),  (0, 1)),
    ]
    |> subtests (description, a, b, expected), description
        assert rational(a) - rational(b) == rational(expected)
    end
end

test "multiplication"
    [
        ("Multiply two positive rational numbers", (1, 2), (2, 3), (1, 3)),
        (
            "Multiply a negative rational number by a positive rational number",
            (-1, 2),
            (2, 3),
            (-1, 3),
        ),
        ("Multiply two negative rational numbers",       (-1, 2), (-2, 3), (1, 3)),
        ("Multiply a rational number by its reciprocal", (1, 2),  (2, 1),  (1, 1)),
        ("Multiply a rational number by 1",              (1, 2),  (1, 1),  (1, 2)),
        ("Multiply a rational number by 0",              (1, 2),  (0, 1),  (0, 1)),
    ]
    |> subtests (description, a, b, expected), description
        assert rational(a) * rational(b) == rational(expected)
    end
end

test "division"
    [
        ("Divide two positive rational numbers", (1, 2), (2, 3), (3, 4)),
        (
            "Divide a positive rational number by a negative rational number",
            (1, 2),
            (-2, 3),
            (-3, 4),
        ),
        ("Divide two negative rational numbers", (-1, 2), (-2, 3), (3, 4)),
        ("Divide a rational number by 1",        (1, 2),  (1, 1),  (1, 2)),
    ]
    |> subtests (description, a, b, expected), description
        assert rational(a) / NonZeroRational.try_from(rational(b))! == rational(expected)
    end
end

test "absolute value"
    [
        ("Absolute value of a positive rational number", (1, 2), (1, 2)),
        (
            "Absolute value of a positive rational number with negative numerator and denominator",
            (-1, -2),
            (1, 2),
        ),
        ("Absolute value of a negative rational number", (-1, 2), (1, 2)),
        (
            "Absolute value of a negative rational number with negative denominator",
            (1, -2),
            (1, 2),
        ),
        ("Absolute value of zero",                                         (0, 1), (0, 1)),
        ("Absolute value of a rational number is reduced to lowest terms", (2, 4), (1, 2)),
    ]
    |> subtests (description, r, expected), description
        assert Rational.abs(rational(r)) == rational(expected)
    end
end

test "a rational to an integer power"
    [
        ("Raise a positive rational number to a positive integer power", (1, 2),  3,  (1, 8)),
        ("Raise a negative rational number to a positive integer power", (-1, 2), 3,  (-1, 8)),
        ("Raise a positive rational number to a negative integer power", (3, 5),  -2, (25, 9)),
        (
            "Raise a negative rational number to an even negative integer power",
            (-3, 5),
            -2,
            (25, 9),
        ),
        (
            "Raise a negative rational number to an odd negative integer power",
            (-3, 5),
            -3,
            (-125, 27),
        ),
        ("Raise zero to an integer power",                        (0, 1),  5, (0, 1)),
        ("Raise one to an integer power",                         (1, 1),  4, (1, 1)),
        ("Raise a positive rational number to the power of zero", (1, 2),  0, (1, 1)),
        ("Raise a negative rational number to the power of zero", (-1, 2), 0, (1, 1)),
    ]
    |> subtests (description, r, n, expected), description
        assert Rational.pow(rational(r), n) == rational(expected)
    end
end

test "a real number to a rational power"
    [
        ("Raise a real number to a positive rational number", 8.0, (4, 3),  16.0),
        ("Raise a real number to a negative rational number", 9.0, (-1, 2), 0.3333333333333333),
        ("Raise a real number to a zero rational number",     2.0, (0, 1),  1.0),
    ]
    |> subtests (description, x, r, expected), description
        assert x |> Rational.raise(rational(r)) |> Float.equal_within(expected, 1e-12)
    end
end

test "reduction to lowest terms"
    [
        ("Reduce a positive rational number to lowest terms", (2, 4),  (1, 2)),
        ("Reduce places the minus sign on the numerator",     (3, -4), (-3, 4)),
        ("Reduce a negative rational number to lowest terms", (-4, 6), (-2, 3)),
        (
            "Reduce a rational number with a negative denominator to lowest terms",
            (3, -9),
            (-1, 3),
        ),
        ("Reduce zero to lowest terms",       (0, 6),   (0, 1)),
        ("Reduce an integer to lowest terms", (-14, 7), (-2, 1)),
        ("Reduce one to lowest terms",        (13, 13), (1, 1)),
    ]
    |> subtests (description, r, expected), description
        reduced = rational(r)
        assert (Rational.numerator(reduced), Rational.denominator(reduced)) == expected
    end
end
  • Rational is an opaque struct that is always in lowest terms with a positive denominator. Rational.new is the only way to make one, so ==, with no Equatable of its own, compares two rationals by their fields, and 1/2 == 2/4 holds because both are stored as 1/2.
  • Rational.new reduces by dividing both parts by their greatest common divisor times the denominator’s sign, which also moves a minus sign to the numerator. The denominator is a NonZeroInt and the stored one a PositiveInt, so the divisor the reduction uses is never zero; the test helper checks each canonical denominator with NonZeroInt.try_from(...)!.
  • The four operations are Add, Subtract, Multiply and Divide impls, so the tests write a + b and a / b. Divide takes a NonZeroRational, a subtype of Rational whose numerator is not zero, as Int’s / takes a NonZeroInt, so the tests check each divisor with NonZeroRational.try_from(...)!. Each builds its result with Rational.new, which reduces it. The impl functions name their parameters lhs and rhs, as the interfaces do; the checker requires the interface’s names.
  • Rational.pow raises the reciprocal for a negative exponent, with Int.pow on each part. Rational.raise raises a Float to a rational power through Float.pow and the exponent as a Float.
  • Rational.numerator and Rational.denominator read the parts, since the struct is opaque. The reduction cases check the parts, which is what “reduced” means; the other cases compare rationals.
  • The real-power cases compare with Float.equal_within(actual, expected, 1e-12): eight to the power 4/3 is 15.999999999999998, not the canonical 16.0, and rounding to a fixed number of places does not fit the canonical 0.3333333333333333.
  • The tests write each rational as the canonical (numerator, denominator) pair and build it with a rational helper, so every row reads like the canonical data. Each canonical group is one subtests table.