Steve Zeidler is a New York-based consultant programming in C, C++, xBase, BASIC, and Pascal. He owns Financial Computer Services, Inc., and can be reached on CompuServe at 76605, 3373.
The cumulative representational errors that occur when using floating point routines lead to loss of mathematical precision. This article shows how to avoid these representational errors when doing fractional, or fixed slash math in C++.
Creating Classes
According to Knuth, fraction manipulation is a form of rational arithmetic. That is, the numbers (numerators and denominators) represent integer pairs. Since we will only deal with whole number units, hence the tie to the rational number system.The four operations performed on them (addition, subtraction, multiplication, and division) require the finding of the greatest common divisor. Resolving this also reduces answers to their lowest terms. Knowing that all four operations require the same function call is in itself an object-oriented concept.
Under traditional C, or any structured language, I may create a function called gcd and leave it at that. However, under C++, I may create a class called gcd which another class can inherit.
In the source code shown in Listing 1, lines five through 10 create such a class. It has several variables declared private to that class, and one public function. I next create a class called fraction. Now the whole concept of a fraction gets enveloped by a class as well.
A fraction has a numerator and a denominator as well as the four mathematical operations that apply to them. Listed in the source code for the fraction class are these operations, as well as the assignment = and Boolean operators.
In addition, the fraction class names gcd_cls as an inherited one. Specifically, it creates a private instance of it. This means that any function in the fraction class may call the public function within the gcd_cls directly. However, it may not access the variables of gcd_cls except through the gcd_cls function calls.
Further, the keyword private means that this is as far as elements of gcd_cls go. If fraction is itself inherited, the only path to gcd_cls is through fraction. You may overcome this by substituting the keyword private with public. For example:
class gcd_cls { // base class unsigned long u,v,r; public: unsigned long gcd (unsigned long a,unsigned long b); }; class fraction : public gcd_cls { //derived class with public access //to gcd_cls function gcd()In the previous example, the gcd_cls base class is re-cast public. If fraction gets inherited, the public function gcd in gcd_cls will now be directly callable from the new class. As I originally wrote it, this is not the case.This gives you the idea of the kind of data and function hiding available under object-oriented code. Once I decided to go down the fraction tree, I felt that only fraction functions should have access to gcd. This process of data and function hiding by another class is called encapsulation.
Defining The Relationship Between Classes
A relationship that is important to note is the hierarchy between gcd_cls and fraction. The simplest way to say this is that I wrote gcd_cls first, and fraction second. A little insight, however, reveals that fraction needs gcd_cls to work, not the other way around.This seems a better way to explain the relationship. It also illustrates the bond between base and derived classes. A base class is core or essential to its derived class or classes. It's sort of like saying Adam and Eve are essential to the class of the human race, or water is essential to swimming, or love is essential to marriage, or light is essential to photosynthesis.
Writing The Code
Now that I have the relationship between classes squared away, I can begin writing the algorithmic code. Unlike structured code which permits you to start blasting away at your keyboard, object-oriented code forces you to think about relationships between classes first.Look closely at the fraction class. The variables private to that class represent the numerator, n, and denominator, np. The public section contains the prototypes for the overloaded mathematical operators and a few housekeeping functions.
The easiest math operator to overload is the equal sign. Consider the following section.
fraction fraction :: operator=(fraction x) //overload = { n=x.n; np=x.np; return (*this); }Note the function declaration contains only one argument. The implied second argument is the class receiving the result. In fact, C++ uses the keyword this to point to the implied instance.Another way to think of this call is to mentally picture it being written as this=(fraction x). This numerator and this denominator receive the values of their counterparts to the right of the equal sign. Once accomplished, return this.
The double colon, ::, separates the operation from its class. Called the scope resolution operator, it identifies to the compiler which operation and class to use. This leads us to the topic of polymorphism.
The scope resolution operator in the previous example enables us to redefine the usual meaning of the equal sign. If the variables on both sides of the equal sign are of the type fraction, the operation takes place. We created a new meaning for the equal operator.
Bear in mind that the old meaning still stands. However, now the equal sign no longer presents a rigid thing to us, we can change its purpose to suit our needs. Since its use depends on the type of variables we use, or classes we create, it has many meanings. This is polymorphism.
With this in mind, I can now go forward and re-define the denotation of the mathematical operators to deal with fractions. According to Knuth, it is more complex to add or subtract fractions than multiply or divide them.
fraction fraction :: operator+(fraction x) // overload + { fraction w; long d1,t,d2; d1=gcd(np,x.np); if (d1==1) { w.n= (n*x.np)+(np*x.n); w.np= (np*x.rip); return w; } if (d1>1) { t=n*(x.np/d1)+x.n*(np/d1); d2=gcd(t,d1); w.n=t/d2; w.np=(np/d1)*(x.np/d2); return w; } }Knuth states that to avoid working with large numbers, start by calculating the gcd of the two denominators. Since we are overloading the plus operator, np and x.np represent these variables. Note the dot operator to reference the denominator of the variable to the right of the plus sign. This is similar to referencing a structure member locally or a record member in Pascal.The implied denominator to the left of the plus sign needs no special reference.
According to Knuth, 61 percent of the time the gcd of the two denominators will resolve to 1. The rest of the time, it will be larger. Therefore, it pays to single out this occurrence with a special algorithm.
The above function incorporates both methods. In either case, I need a local instance of a fraction, w, to hold the answer. Notice that to create such a local instance, all I had to do was prefix the variable with the class name, fraction w.
Just like other structured languages, the new variable will absorb the algorithmic manipulations and return the results. The calling variables remain untouched. Again, the black box idea comes into play.
Subtraction is simply a variation on the above theme. Although not obligatory, I created local instances of fractions to replace the arguments on both sides of the minus operator.
fraction w,tmpa,tmpb; long d1,t,d2; tmpa=*this; tmpb=x;I did this to prove to myself the ability of C++ to further hide data within class functions. Like regular C, C++ copies arguments on to the stack in function calls. Much to my surprise, and delight, it follows closely the Pascal method for reference pointing. That is, in Pascal, the key word var preceeds referenced arguments within a functions call list. C++ allows the & symbol to act in the same manner.I used this method in the overloading of the Boolean operators. This seems far superior to using the ampersand in a call, and asterisks in the called list.
Rounding out the suite of routines are the input and output overloads. Being able to plug into and out of streams is a pleasure. The cin and cout commands will mix and match fractional types with anything.
To accomplish the same in traditional C would require a host of arguments within the printf statement. Forget about scanf. This method is clearly superior and much cleaner.
I suppose, while I'm on the subject of streams, I should point out my violation of object-oriented canons. In the referenced section, I use gotoxy commands. Since I'm tooling around in my Turbo C++ compiler, this seemed a simple way to place the slash bar on the screen and manipulate the cursor.
However, it does contradict pure OOP theory. What I need here is a class of screen manipulators.
The above routines may not illustrate the cleanest approach to incorporating fractional, or fixed slash, routines into object oriented classes. They do, however, represent a new methodology and approach to programming. The final step is getting rid of the main function and renaming the above a header (ie., fracs.h). This provides a true black-box extension to your tool kit.
As the program stands, you can compile it under Turbo C++ and run it as a standalone.
There is one final step left to be done. My fraction class handles numerators and denominators only. The next step is to add the logic to handle whole number components. For example, it would be nice to pass the class a value such as 5 3/32 instead of its pure equivalent fraction 163/32. I'll work on it.