Rational implementation

Question

Can someone review this?

The header file can be viewed here.

#include <stdio.h>
#include <stdbool.h>
#include <math.h> // searches default library classpaths
#include "Rational.h" // searchs my directory
// let's the compiler know that this is a function
static bool Rational_isPositive(Rational rational);
static double absolute(double number);

/**
 *  Creates and initializes a new Rational object.
 *  Pre:
 *        Denominator != 0
 *  Returns:
 *        A Rational object X such that X.Top == Numerator
 *        and X.Bottom = Denominator.
 */
Rational Rational_Construct(int Numerator, int Denominator) {
  // make all rationals into the equivalent rational with
  // either a postive or negative numerator and never a 
  // negative denominator
  Rational newRational;
  if (Numerator < 0 && Denominator < 0) {
    Numerator = -Numerator;
    Denominator = -Denominator;
  } else if (Numerator >= 0 && Denominator < 0) {
    Numerator = -Numerator;
    Denominator = -Denominator;
  } 

  newRational.Top = Numerator;
  if (Denominator != 0) {
    newRational.Bottom = Denominator;
  } else {
    printf("You have set a denominator = 0");
    newRational.Bottom = 0;
  }
  return newRational;
}

/**
 *   Compute the arithmetic negation of R.
 *   Pre:
 *        R has been properly initialized.
 *   Returns:
 *        A Rational object X such that X + R = 0.
 */
Rational Rational_Negate(const Rational R) {
  Rational negatedR;
  negatedR.Top = -R.Top;
  negatedR.Bottom = R.Bottom;
  return negatedR;
}

/**
 *   Compute the arithmetic floor of R.
 *   Pre:
 *        R has been properly initialized.
 *   Returns:
 *        The largest integer N such that N <= R.
 */
int Rational_Floor(const Rational R) {
  if (Rational_isPositive(R)) {
    return R.Top / R.Bottom;
  } else {
    if (R.Top % R.Bottom == 0) {
      return R.Top / R.Bottom;
    } else {
      return R.Top / R.Bottom - 1;
    }
  }
}

/**
 *   Compute the arithmetic ceiling of R.
 *   Pre:
 *        R has been properly initialized.
 *   Returns:
 *        The smallest integer N such that N >= R.
 */
int Rational_Ceiling(const Rational R) {
  if (Rational_isPositive(R)) {
    if (R.Top % R.Bottom == 0) {
      return R.Top / R.Bottom;  
    } else {
      return R.Top / R.Bottom + 1;
    }
  } else {
    return R.Top / R.Bottom;
  }
}

/**
 *   Round R to the nearest integer.
 *   Pre:
 *        R has been properly initialized.
 *   Returns:
 *        The closest integer N to R.
 */
int Rational_Round(const Rational R) { 
  double decimalFormat = (double) R.Top / (double) R.Bottom;
  double R_ceiling = (double) Rational_Ceiling(R);
  double R_floor = (double) Rational_Floor(R);
  double distanceToR_ceiling = absolute(R_ceiling - decimalFormat);
  double distanceToR_floor = absolute(R_floor - decimalFormat);

  // decimalFormat is closer to the ceiling
  if (distanceToR_ceiling < distanceToR_floor) {
    return (int) R_ceiling;
  } else {
    return (int) R_floor;
  }
}

/**
 *   Compute the sum of Left and Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        A Rational object X equal to Left + Right.
 */
Rational Rational_Add(const Rational Left, const Rational Right) {
  Rational sum;
  sum.Top = (Left.Top * Right.Bottom) + (Right.Top * Left.Bottom);
  sum.Bottom = Left.Bottom * Right.Bottom;
  return sum;
}

/**
 *   Compute the difference of Left and Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        A Rational object X equal to Left - Right.
 */
Rational Rational_Subtract(const Rational Left, const Rational Right) {
  Rational sum;
  sum.Top = (Left.Top * Right.Bottom) - (Right.Top * Left.Bottom);
  sum.Bottom = Left.Bottom * Right.Bottom;
  return sum;
}

/**
 *   Compute the product of Left and Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        A Rational object X equal to Left * Right.
 */
Rational Rational_Multiply(const Rational Left, const Rational Right) {
  Rational product;
  product.Top = Left.Top * Right.Top;
  product.Bottom = Left.Bottom * Right.Bottom;
  return product;
}

/**
 *   Compute the quotient of Left and Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *        Right != 0.
 *   Returns:
 *        A Rational object X equal to Left / Right.
 */
Rational Rational_Divide(const Rational Left, const Rational Right) {
  Rational quotient;
  quotient.Top = Left.Top * Right.Bottom;
  quotient.Bottom = Left.Bottom * Right.Top;
  return quotient;
}

/**
 *   Determine whether Left and Right are equal.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left == Right, false otherwise.
 */
bool Rational_Equals(const Rational Left, const Rational Right) {
  if (Left.Top * Right.Bottom == Left.Bottom * Right.Top) {
    return true;
  } else {
    return false;
  }
}

/**
 *   Determine whether Left and Right are not equal.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left != Right, false otherwise.
 */
bool Rational_NotEquals(const Rational Left, const Rational Right) {
  if (Rational_Equals(Left, Right)) {
    return false;
  } else {
    return true;
  }
}

/**
 *   Determine whether Left is less than Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left < Right, false otherwise.
 */
bool Rational_LessThan(const Rational Left, const Rational Right) {
  // double leftValue = (double) Left.Top / (double) Left.Bottom;
  // double rightValue = (double) Right.Top / (double) Right.Bottom;
  int leftValue = Left.Top * Right.Bottom;
  int rightValue = Left.Bottom * Right.Top;
  if (leftValue < rightValue) {
    return true;
  } else {
    return false;
  }
}

/**
 *   Determine whether Left is less than or equal to Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left <= Right, false otherwise.
 */
bool Rational_LessThanOrEqual(const Rational Left, const Rational Right) {
  if( Rational_Equals(Left, Right) | Rational_LessThan(Left, Right)) {
    return true;
  } else {
    return false;
  }
}

/**
 *   Determine whether Left is greater than Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left > Right, false otherwise.
 */
bool Rational_GreaterThan(const Rational Left, const Rational Right) {
  if (Rational_LessThanOrEqual(Left, Right)) {
    return false;
  } else {
    return true;
  }
}

/**
 *   Determine whether Left is greater than or equal to Right.
 *   Pre:
 *        Left and Right have been properly initialized.
 *   Returns:
 *        True if Left >= Right, false otherwise.
 */
bool Rational_GreaterThanOrEqual(const Rational Left, const Rational Right) {
  if (Rational_GreaterThan(Left, Right) | Rational_Equals(Left, Right)) {
    return true;
  } else {
    return false;
  }
}

/**
 *   Determines if rational is positive.
 *   Pre: rational has been properly initialized.
 *   Returns: True if rational >=0, false otherwise.
 */
static bool Rational_isPositive(Rational rational) {
  // all rationals are equivalently represented without a negative
  // denominator
  if (rational.Top >= 0) {
    return true;
  } else {
    return false;
  }
}

/**
 *   Computes absolute value of a double number.
 */
static double absolute(double number) {
  if (number < 0) {
    return -number;
  } else {
    return number;
  }
}

Answer 1

1. I like that you are treating your rationals as immutable by returning new rationals from all your operations.

2. Your naming conventions are a bit unusual. In most C like languages (C, C++, C#, Java) local variables and parameters are camelCase. Specifically in C method names tend to be camelCase or snake_case.

3. You are using the mathematical terms Numerator and Denominator for the parameters of you construction function however you use Top and Bottom for the properties of you Rational type which seems a bit unusual - why not stick to the mathematical terms?

4. When someone passes in a Denominator which is 0 you just have a printf in there.

   • If anything it should print at least to stderr.
   • It doesn't really alert the programer to the error and just fails in some later operations anyway (like Round, Floor, Ceil).

   Consider forcing the error by causing the div by zero right there or changing the interface of the method to:

   bool Rational_Construct(int numerator, int denominator, Rational* result)
   

   and return false if the input is invalid.

5. Most of your comparisons like this

   if (Left.Top * Right.Bottom == Left.Bottom * Right.Top) {
       return true;
   } else {
       return false;
   }
   

   can be shortened to

   return Left.Top * Right.Bottom == Left.Bottom * Right.Top;
   

Answer 2

In addition to ChrisWue's comments, I'd add:

1. In this block of code:

   if (Numerator < 0 && Denominator < 0) {
     Numerator = -Numerator;
     Denominator = -Denominator;
   } else if (Numerator >= 0 && Denominator < 0) {
     Numerator = -Numerator;
     Denominator = -Denominator;
   } 
   

   both branches do the same thing, so you could combine them into one condition:

   if (Numerator < 0 && Denominator < 0 || Numerator >= 0 && Denominator < 0) {
     Numerator = -Numerator;
     Denominator = -Denominator;
   }
   

   Now both parts of the condition have Denominator < 0, so you could write:

   if ((Numerator < 0 || Numerator >= 0) && Denominator < 0) {
     Numerator = -Numerator;
     Denominator = -Denominator;
   }
   

   Now it's clear that the condition Numerator < 0 || Numerator >= 0 is always true, so it can be dropped, leaving:

   if (Denominator < 0) {
     Numerator = -Numerator;
     Denominator = -Denominator;
   }
   

2. In the comment for Rational_Construct you specify a precondition Denominator != 0. But if the caller passes in zero, then you just print a message to standard output. It would be better to write:

   assert(Denominator != 0)
   

   so that the program aborts. Having rationals with denominator 0 leads to many sorts of trouble: for example the rational ⁰/₀ compares equal to every other rational.

3. The comment for Rational_Construct says that it returns:

   A Rational object X such that X.Top == Numerator and X.Bottom = Denominator.
   

   but in fact this is not true, since the denominator may be negated. Instead it should say something like:

   A Rational object R such that R.Top/R.Bottom == Numerator/Denominator.
   

4. Your operator implementations don't call Rational_Construct: they just build a new Rational structure however they please. This means that the consistency checks in Rational_Construct (such as making sure that the denominator is positive) are skipped.

   It would result in shorter and more reliable code if you always called Rational_Construct. For example:

   Rational Rational_Negate(const Rational R) {
     return Rational_Construct(-R.Top, R.Bottom);
   }
   
   Rational Rational_Add(const Rational Left, const Rational Right) {
     return Rational_Construct(Left.Top * Right.Bottom + Right.Top * Left.Bottom,
                               Left.Bottom * Right.Bottom);
   }
   

5. Even small computations with your rationals result in integer overflow. For example, consider the following program:

   int main(int argc, char **argv) {
       Rational sixteenth = Rational_Construct(1, 16);
       Rational sum = Rational_Construct(0, 1);
       int i;
       for (i = 0; i < 10; ++i) {
           sum = Rational_Add(sum, sixteenth);
           printf("%d/%d\n", sum.Top, sum.Bottom);
       }
       return 0;
   }
   

   The program looks as if it is supposed to add ¹/₁₆ ten times, getting the result ¹⁰/₁₆. But it actually has undefined behaviour due to signed integer overflow. On my computer it prints:

   1/16
   32/256
   768/4096
   16384/65536
   327680/1048576
   6291456/16777216
   117440512/268435456
   -2147483648/0
   0/0
   0/0
   

   Now, because you're using C's fixed-size integers, there are bound to be computations whose results are too large to be represented. But it would be better to raise an error when the result is too large, rather than causing undefined behaviour. And you should at the very least make some effort to ensure that integer overflow doesn't happen in small examples like this: when we add ¹/₁₆ ten times we ought to be able to get ¹⁰/₁₆.

   An easy way to avoid integer overflow in small examples is to always reduce rationals to their lowest terms (thus turning ²/₄ as ¹/₂). For example, you could do this:

   #include <assert.h> /* for the assert() prototype */
   #include <limits.h> /* for INT_MIN */
   #include <stdlib.h> /* for the abs() prototype */
   
   Rational Rational_Construct(int Numerator, int Denominator) {
     /* Ensure that Denominator is positive */
     assert(Denominator != 0);
     if (Denominator < 0) {
       assert(Numerator != INT_MIN);
       assert(Denominator != INT_MIN);
       Numerator = -Numerator;
       Denominator = -Denominator;
     }
   
     /* Find the greatest common divisor of Numerator and Denominator. */
     int a = abs(Numerator), b = Denominator;
     while (b) {
       int c = a % b;
       a = b;
       b = c;
     }
   
     /* Reduce the fraction to lowest terms. */
     Rational newRational;
     newRational.Top = Numerator / a;
     newRational.Bottom = Denominator / a;
     return newRational;
   }
   

   Now the program I gave above prints:

   1/16
   1/8
   3/16
   1/4
   5/16
   3/8
   7/16
   1/2
   9/16
   5/8
   

   (Of course this doesn't solve the integer overflow problem in the general case, but at least it allows small programs like this to complete successfully.)

Answer 3

1. Usually only one of the two scalars of a rational has a sign and usually the so-called numerator is the scalar having the sign. This in turn would translate to:

    typedef struct {
      int Numerator;
      unsigned Denominator;
    } Rational;
   

This choice will gift you with less code for the sign management and 1 extra bit of data.

2. Denominators cannot be zero, unless you want to have a wasteful number of representations of the infinity and really need to handle them in operations. So denominators should be represented as n-1, that is you write 0 (zero) but actually mean 1 (one). Maybe a little bit more code but an extra value for denominators and extra precision.

3. There is another simple representation trick that will save you the wasteful number of representations of the zero. Again, you get a little bit of extra code but will gain you some more room to represent numbers. But this very one is left as an exercise to the keen coder.