A Library for Integer Math Operations
In this example, I will demonstrate how you might create a library of functions. There is only one main function in any C program. The rest of the program is composed of other functions. Thus most of one's time programming is spent writing functions other than main. In fact you could spend weeks—even years—working as a programmer and never write a single line in function main. Many programmers spend their time building libraries of functions that will be used by other programmers. I will do that here in this example.
Since we haven't covered arrays, strings, or files yet I will make this little library mathematical. In it I will include a number of loosely related functions for doing some interesting things with integers. Some of my functions may require more mathematical background than you are comfortable with, but most of them should be easy enough to understand. In any case, the primary point here is to see how I set up the library. What it does is less significant.
First, I need to have a specification of the functions I am to write. This material would be in a header file (.h file). The specification is, in effect, the contract between me as the implementer of the library and the person who wishes to use the library. Notice that I have no idea how these functions will be used. I offer them only in the hope that they will be useful to someone eventually. This is called "bottom-up" programming. It contrasts with the "top-down" programming people do when they work on an application. There is no application here; there is no main function.
Here is the header file, named imath.h. It contains declarations of the functions I'm going to implement and a description of their parameters, return values, and operation. This information is my contract with the library user. It must be clear and complete.
int factorial(int N);
/* This function computes N! and returns the result. N! is found by
multiplying N * (N-1) * (N-2) * ... * 1. Zero factorial is 1 by
definition. Negative values of N yield undefined behavior. If N!
overflows int, the effect is undefined. */
int GCD(int A, int B);
/* This function returns the greatest common divisor (GCD) of A and
B. The GCD is the largest integer that will divide into both A
and B evenly. It is useful for reducing fractions. This function
assumes A and B are positive. */
int raise_power(int base, int exponent);
/* This function raises base to the power of exponent. It uses a
special method which allows it to execute much faster than by
just "multiplying it out." In particular it executes in a time
proportional to the log base 2 of exponent. If the result overflows
integer or if exponent is negative the effect is undefined. */
int combinations(int group, int total);
/* This function returns the number of different ways you can take
group items from a collection of total items. For example, if you
had 10 distinct marbles, how many different sets of three could
you make from the 10. The call combinations(3, 10) would tell you.
This function assumes total >= group and that both total and group
are positive, non-zero values. */
int permutations(int group, int total);
/* This function is similar to combinations except that it regards
different orderings of the items in group as distinct. This
function has the same restrictions on its use as Combinations. */
There are other functions I could imagine including (like my is_prime from earlier examples), but this will get me started for now. How will these functions be used? Who knows? However, I think you could imagine a program that might want to use one or more of them.
To start the .c file, I will first copy the declarations of all the functions, remove the semicolons at the end of those declarations and add braces. I will also put an error message into each one so that if anyone tries to use it they will find out that it doesn't (yet) work. I will call the resulting file imath.c.
#include <stdio.h> /* Only needed for the error message. */
#include "imath.h" /* Good idea to #include this too. */
/*
* int factorial(int N)
*
*/
int factorial(int N)
{
printf("Sorry! factorial() is not yet implemented.\n");
}
/*
* int GCD(int A, int B)
*
*/
int GCD(int A, int B)
{
printf("Sorry! GCD() is not yet implemented.\n");
}
/*
* int raise_power(int base, int exponent)
*
*/
int raise_power(int base, int exponent)
{
printf("Sorry! raise_power() is not yet implemented.\n");
}
/*
* int combinations(int group, int total)
*
*/
int combinations(int group, int total)
{
printf("Sorry! combinations() is not yet implemented.\n");
}
/*
* int permutations(int group, int total)
*
*/
int permutations(int group, int total)
{
printf("Sorry! permutations() is not yet implemented.\n");
}
Notice how I put a comment block in front of each function. This is required by the VTC style guide. Typically you would put information about the function's parameters, return value, and meaning in that block. In this case, that information is in the header file and it would be better not to duplicate it (since that can lead to errors when you forget to update one copy after making a change). Instead in this case I will put information in the function header about how the function works. I will leave the "what" question for the header file to answer. If you write a function that does not have a declaration in a header file, you should put both "how" and "what" information in its comment.
My current imath.c is complete in the sense that it should compile. Of course the functions don't do anything right now, but that's fine. I will try to compile it anyway.
$ cc -c imath.c
I supply the -c option to the compiler so that it does not try to link my program into an executable file. That wouldn't make sense because there is no main here. Notice that I don't need to say anything about imath.h when I compile the file. This is because imath.h is read by the compiler automatically due to the #include in imath.c.
Good no errors!
Now I will implement these functions one at a time. As I work on each one I can focus my mind totally on that function. I do not need to worry about how I will do the others. let me start with factorial.
int factorial(int N)
{
int result = 1;
// Handle 0! as a special case. Just return 1 at once.
if (N == 0) return result;
// Keep looping until N == 1. Multiply N into Result as I go.
while (N > 1) {
result *= N;
N--;
}
return result;
}
That should be about it. This single function is not too complicated. Yet keep in mind that it might be part of an enormous program. This is how large, complicated programs get created: one function at a time. Notice that I'm ignoring negative values for N. That's okay, though, because the specification for factorial said that negative values cause "undefined behavior". The user should never send me such a value and if he/she does, what happens is not my concern. As a library implementer, I like "undefined behavior". It makes my life easier.
Now let me compile imath.c again. If there are syntax errors in what I wrote, the compiler will let me know... No problems!
Now... I suppose it would be a good idea to test this function. The fact that the compiler accepted it is good, but certainly that does not prove that it will work. In order to test my library I'll need a special program to use as a "test fixture". This program will contain a main but do nothing more than exercise my functions. Creating text fixture programs is a pain, but it is necessary if you want a reliable library.
Here is my first text fixture for the imath library. It is in a file named imath_test.c
#include <stdio.h>
#include "imath.h"
int main(void)
{
int number;
// Get a value from the user.
printf("What number? ");
scanf("%d", &number);
// Run the factorial function and print the result.
printf("%d! is %d\n", number, factorial(number));
return 0;
}
I compiled this with the imath library using a command like this
$ cc -o imath_test imath_test.c imath.c
Notice how I named the final executable file imath_test and not imath. I did this because imath_test is the program (it contains main). The library is not a program. It is just a collection of functions.
Things look good. The factorial function appears to work as desired.
Now I will write the next function. Which one looks good? I tend to write the easy ones first to give myself encouragement and confidence. Right now I'll do the GCD function. It turns out it's easy to compute the greatest common divisor using a method known as Euclid's Algorithm. Of course I don't remember it, but I can look it up. From "Fundamentals of Sequential and Parallel Algorithms" by Kenneth Berman and Jerome Paul (PWS Publishing Company, (C) 1997, ISBN=053494674-7), page 5 shows pseduo-code for Euclid's Algorithm.
int GCD(int A, int B)
{
int remainder;
while (B != 0) {
remainder = A % B;
A = B;
B = remainder;
}
return A;
}
To test this, I modify my test fixture as follows
#include <stdio.h>
#include "imath.h"
int main(void)
{
int choice;
int number;
int A, B;
// Ask the user what needs to be tested.
printf("\nSelect a test:\n\n");
printf("1) factorial\n");
printf("2) GCD\n");
scanf("%d", &choice);
printf("\n");
// Perform the appropriate test.
switch (choice) {
case 1:
// Get the value from the user.
printf("What number? ");
scanf("%d", &number);
// Run the Factorial function and print the result.
printf("%d factorial is %d\n", number, factorial(number));
break;
case 2:
// Get values from the user.
printf("What numbers? ");
scanf("%d %d", &A, &B);
// Run the GCD function and print the result.
printf("The GCD of %d and %d is %d\n", A, B, GCD(A, B));
break;
}
return 0;
}
This test fixture seems complicated because I want it to support not only the new function but also the earlier one. This test fixture is not a "throw away" program. It will be saved along with the source of the imath library itself. If one of the imath functions is later modified, this test fixture could then be used again to exercise it. Alternatively if one of the imath functions is found to have a bug, this test fixture could be used to reproduce the bug and serve as a starting point for debugging. Because the test fixture is going to be around for as long as the library is around, it should be created with the same respect and attention to detail as any other program.
Okay... the GCD function seems to be working okay.
Next I will write the raise_power function. To improve performance, I will use a tricky algorithm that works much faster than the obvious way of doing this operation. See imath.c for the details.
After writing raise_power I again modify the test fixture so that I can exercise it. See imath_test.c for the details.
So far everything is going together fine. I'm lucky! If any of these functions failed to work properly, however, I could then focus on just debugging that one function. Never try to do too much at once. If you do, it won't work and you won't know where to start looking for your problem.
The next function is combinations. This function is supposed to calculate the number of different ways I can select a small set of objects from a large set where the order in which I select objects is not relevant. (Different orders don't make for a different selection). It happens that there is a formula for this. It can be found in any probability and statistics text. Basically if I'm choosing k things from a set of n objects the number of combinations is
C = n! / (k! * (n-k)!)
Here I'm using the '!' notation to mean "factorial" in the traditional manner. Well... it happens that I already have a function that can compute factorials. So I will use it. Here is my combinations function
int combinations(int group, int total)
{
return factorial(total) / (factorial(group) * factorial(total - group));
}
Simple! There is no reason why, when creating a library, you can't use the very functions you are creating. In fact it is often done. The user of your library might not be aware that when he/she calls combinations, your factorial function is also being used. That's fine. Why should the user of your library need to know that? As long as your functions all do what they should everything works.
It turns out that the permutations function can be written in terms of the combinations function. This is because
P = k! * C(k, n)
Or, in C:
int permutations(int group, int total)
{
return factorial(group) * combinations(group, total);
}
This process of building functions on top of other functions is common and essential. You should get used to seeing it. The final library is now in imath.h and imath.c. The final test fixture is in imath_test.c.
Here I will stop work on the imath library for now. All the functions have been written and they all work. In theory the files imath.c (or its compiled version, imath.o) and imath.h could now be presented to another programming team for their use. That other team would not need the test fixture, but I would want to keep it so that I could follow up more effectively on bug reports.
There are issues with this imath library. In particular my method of computing combinations and permutations is not ideal. Those functions currently use the factorial function. While that made it easy to write them it also introduced problems. Factorials grow very rapidly and so factorial(N) tends to overflow the range on integers except for when N is small. In combinations (and permutations) two large factorials get divided. Yet those functions as written can't handle that situation since errors are introduced by overflow before the division happens. As a result the current combinations and permutations functions only work properly with small input numbers. This matter can and should be fixed.
I leave that as an exercise for the reader!
© Copyright 2003 by Peter C. Chapin.