P.J. LaBrocca is the author of ReCalc(TM), a set of rational expression calculators that never give answers (well, almost never), and run identically on PCs, Macintoshes, and Apples. He has a BS and MA in Chemistry and teaches computer science at Peter Rouget Middle School 88 in Brooklyn, NY 13782, (607) 746-7175.
Introduction
This article describes a method of representing and manipulating mixed numbers in C. A simple mixed number calculator, MixCalc, exercises the functions. You can use MixCalc to help you do your kids' fractions homework.The first part presents the package for working with mixed numbers in a C program. It describes mixed_t, the data structure used to represent mixed numbers, and the functions that do calculations with them. The discussion then turns to MixCalc, a rational number calculator (Listing 1 and Listing 2) . MixCalc accepts infix expressions involving any combination of whole numbers, fractions and mixed numbers and returns an answer as either a whole number, a fraction, or a mixed number. For example, given this input
3 2|3 / ( 1|2 + 2 )MixCalc returns
1 7|15A vertical bar, |, is used as the fraction bar to differentiate it from the division sign.I based the code for MixCalc's parser (Listing 3) on the recursive-descent parser from Bjarne Stroustrup's The C++ Programming Language. I modified it to work with mixed_ts and added some error recovery.
A rational number is any number that can be expressed as the quotient of two whole numbers. Integers are rational numbers. A proper fraction's value is less than one. An improper fraction's value is equal to or greater than one. A mixed number is the sum of an integer and a proper fraction. Since a mixed number can be expressed as an improper fraction it is a rational number. I use the term mixed number loosely to refer to any rational number.
Most programming languages do not provide built-in support for fractions or mixed numbers. You approximate mixed numbers as decimal numbers using floating-point types. For most applications this is fine. However, mixed numbers have one big advantage over decimal numbers — they are always exact. Using decimal numbers, 1 divided by 3 results in the approximation 0.33333...; the mixed number result is exactly 1|3. Of course, there is a down side. In certain calculations the integers used for the numerator and denominator can overflow. However, in an application using, say, the English measuring system, five-eighths looks a lot better as 5|8 than as 0.625.
Mixed Number Package
The data structures and functions for mixed numbers are in Listing 4, Listing 5, Listing 6, Listing 7, and Listing 8, fraction.c, mixed.h, error.c, mix_num2.c, and primes.c.Since I wanted the intermediate results of calculations available for display (for an application not discussed here) I provided storage for each possible component of a mixed number. Integer types are used for the whole number part, the numerator part, the denominator part and the sign. Fractions must be factored into primes in order to reduce them. The factors of the numerator and denominator are stored in a two-dimensional array of integers. Including the arrays rather than pointers to dynamically-allocated storage simplifies the code at the expense of stack size. At compile time, be sure to provide a generous stack.
Include mixed.h in each file that uses the functions, and call init_primes once before doing any calculations. init_primes sets up a table of prime numbers using the sieve of Eratosthenes. Declare mixed numbers using mixed_t. It's a good idea to initialize mixed_ts as soon as possible. You assign values by calling mix_init or mix_clear. mix_init accepts a pointer to a mixed_t, and three integer values for the whole number, numerator, and denominator parts of the mixed number. The sign of the mixed_t is determined by the first integer; the others should be positive. mix_clear sets the mixed number to zero. Both functions truncate the arrays holding the prime factors of the numerators and denominators.
The typedef Integer controls the size of the int used to store the parts of mixed_ts. Use any size as long as it's signed. Naturally, larger ints make overflow less likely, but take more room and time. The output function mix_print, and any input functions you supply, need adjustment if you change the size of Integer. The sign of a mixed_t is stored in an int as +1 or -1. It is used in intermediate calculations.
Notice that a mixed_t with value zero has its whole number and numerator parts set to zero, but its denominator part is set to one. A denominator is also a divisor, and division by zero is meaningless. Also note that a fraction that has not yet been factored has the first elements of its factors array set to one.
The functions for manipulating mixed_ts are in fraction.c. They are used by the functions that perform arithmetic operations on mixed numbers, and for converting mixed numbers to equivalent forms.
To reduce fractions to lowest terms you need to know the prime factors of the numerator and denominator. These are provided by a call to mix_factor. mix_factor takes the address of a mixed number and puts its prime factors into the factors array. The whole number part is not considered. mix_factor is called by mix_reduce, which returns a pointer to a mixed number with the fraction part in lowest terms. mix_reduce loops through the two arrays of factors comparing them element by element, and either ignoring them or multiplying them into temporary variables. For example, consider reducing the fraction 42|90. After the call to mix_factor the arrays look like this:
Numerator 2 3 7 1 Denominator 2 3 3 5 1The pointers top and bottom point to the prime factors under consideration, one from the numerator, the other from the denominator. If the elements are equal, the factors are common. Advancing the pointers cancels the common factors. In the example, the two's, and then the three's are ignored. When the factors are unequal the smaller is multiplied into its temporary variable and its pointer is advanced. This continues until the sentinel, i.e., an element equal to one, is encountered in one or both arrays. Any remaining factors are multiplied into the corresponding temporary variable. The rest of the function adjusts the whole number part, if needed, and makes sure the mixed number is in a consistent state if it started out equal to zero.An improper fraction is one in which the numerator is greater than or equal to the denominator. In the case of the mixed numbers developed here this means that the whole number part must be zero. mix_make_improper converts a mixed_t into an improper fraction. This function is called by mix_add and mix_sub. You can it call before mix_print to display a mixed_t as an improper fraction.
mix_print displays a mixed number on standard output in a reasonable form within the limits of a text-based environment. Some details are presented later.
mix_num2.c contains the functions for doing arithmetic with mixed numbers. The four basic operations are provided, plus negation and calculating the lowest common denominator.
Addition and subtraction are accomplished by converting the mixed numbers to improper fractions, bringing them to a common denominator and adding the numerators. For multiplication the numerators are multiplied, then the denominators. The division function takes the reciprocal of the second mixed number and calls the multiplication function. The possibility of taking the reciprocal of zero presents a complication. As it stands, mix_recip complains if the denominator will become zero. Otherwise it returns the reciprocal. mix_recip does not alter its argument. Your program should check if a mixed number is zero before dividing by it. The arithmetic functions return unreduced results.
mix_neg reverses the sign of a mixed_t. mix_lcd returns the lowest common denominator of two mixed_ts.
If during calculations the numerator becomes zero, the denominator gets set to one. If the value of a mixed number becomes zero the sign is set to positive. These actions ensure a consistent starting point for further calculations.
A greatest_common_divisor function could be used to "pre-reduce" fractions during calculations. However, taking out gcds does not guarantee lowest terms. To ensure lowest terms mix_reduce still has to be called. There might be some practical advantage, say, when adding up a long list of fractions if you avoid overflow. However, 61% of the time random number pairs have a gcd equal to one. Most of the time calling a gcd function adds overhead but little else.
Note that mix_add and mix_sub alter the representation, but not the value, of their arguments. To preserve the original representation copy it to another mixed_t.
Limits
Storing numbers in computer memory has limitations. Range and domain errors are reported for many calculations involving floating-point types. For integer types errors may or may not be reported. If you are lucky bizarre results let you know something is amiss. When working with mixed_ts here are some limits to keep in mind.Whole numbers, numerators and denominators are stored in longs. If the size of a calculation's result doesn't fit in a long the result is wrong. You might get a run-time error or garbage. The functions do not take any precautions.
The largest prime number in the prime number table is 15991. Numbers with prime factors bigger than that produce all kinds of annoying errors. Some examples are given later.
The factors array holds 40 prime factors, a generous amount. If more need to be stored other memory gets over-written with the usual unpredictable results. Actually you might consider reducing the size.
The mixed_ts in this version are big so stack overflow is likely. Increase the amount of stack space allocated at compile and link time as needed.
Scanning a Mixed Number
MixCalc's parser is based on the one presented in Stroustrup's The C++ Programming Language. I discuss only those parts I modified for MixCalc.The main alteration was to the function than scans the input. For MixCalc the scanning function, gettok (Listing 9) , has to recognize mixed numbers in their varying guises. gettok reads the standard input, breaks it up into tokens, returns the tokens to the parser and constructs a mixed_t. If it detects an unrecognized token it issues a diagnostic to standard error and resets MixCalc via a call to longjmp.
The setjmp/longjmp combination provides a good method of error recovery for a calculator program where an error in the input stream makes the rest of the expression meaningless. A variable of type jmp_buf is defined and a call is made to setjmp before entering the main loop. If longjmp is called later on the environment is reset to the way it was when setjmp was called. An error in an expression causes the rest of the current line to be discarded. MixCalc resumes on the next line.
Scanning a mixed number presents a problem similar to scanning a floating-point number. Valid input can come in several forms. An acceptable mixed number may consist of a whole number, a fraction, or a whole number followed by a fraction. An optional sign may precede any of these. An irksome part of scanning a mixed number is that it is natural to have space embedded in it. gettok tackles these problems.
Positive and negative signs are treated as operators, not as part of the mixed number. They are passed to the parser.
When gettok encounters a digit it pulls in an integer using scanf. Then white space is skipped. The next character can be a digit, a fraction bar, or some other character (an operator or an unknown character). If the next character is a digit then the scanner expects an integer, optional white space, a fraction bar, optional white space, and another integer. Otherwise an error message is displayed and MixCalc resets itself. If the next character is a fraction bar then an integer preceded by optional white space must follow. Otherwise an error as above is generated. For each of the three possible successful scans gettok constructs a mixed_t and returns the token NUMBER. Note that the fraction bar is not an operator in MixCalc, rather it is a delimiter.
Compiling MixCalc
MixCalc compiles as presented here with Microsoft C 6.00 or C/C++ 7.0, and Zortech C/C++ 3.0. A makefile (Listing 10) is provided for building MixCalc using Microsoft and Zortech. It's set to use the Microsoft compilers as shipped. To switch to Zortech move the # on the lines referring to the CC macro and the linker. The file works with Microsoft's NMAKE and Zortech's MAKE utilities. I also use this makefile to backup source files and update hardcopy. For example, make backup copies those files that changed since the last backup to a floppy on drive a:. To use backup and hcopy with Zortech's MAKE add exclamation points before the commands.For Microsoft's PWB create a project called mixcalc. Add the seven C files to the project. Then choose build from the project menu. The PWB does not use the makefile provided with MixCalc.
I like to compile everything with the large model, but any model should work. For more information on using MixCalc see the sidebar "How to Use MixCalc."