Adding Rational Types to the C Programming Language

One of the main problems with the C programming language as opposed to something like Python is that it doesn’t provide any of the convenient amenities that more high-level languages provide in terms of abstract data types. Basically, you have to implement everything yourself. C provides integer types and floating point types, and that’s basically it. So implementing something like, say, a rational type requires some extra coding, and can make for a pretty interesting project.

In this tutorial I will show you how I implemented a rational type for the C language. The rational type has an advantage over floating point types in that it represents rational numbers like 2/3 and 3/7 exactly and succinctly without any rounding errors. So it is useful, therefore, to have a rational type in C. I implemented my rational type while writing a small program that demonstrates Bayesian probabilities. Probability theory is probably the best example of a place where you would want to have exact ratios in your programs, because the precise values of the numerator and denominator can tell you a lot more about a probability than the estimated floating point value.

To implement a new numeric type in C (or basically any language for that matter) you need to do two things. First, you need to create a data structure (a struct in this case) that encapsulates all the data needed to specify the number to whatever degree of accuracy is desired. Second, you need to re-implement all the relevant arithmetic operators for the new type.

The definition for my rational type looks like this:


typedef struct {
        int n; // numerator
        int d; // demominator
} rat_t;

That’s it. Just an integer for the numerator and an integer for the denominator. Where rational types get more tricky is in implementing the operations of addition, subtraction, multiplication, and division. For this, we will need to resort to some laws from elementary algebra regarding ratios…

First let’s create a function for initializing our rational type:


void rat_init( rat_t *r, int n, int d ){
        r->n = n;
        r->d = d;
}

One problem that comes up in C programming is in writing functions that create variables to be used by calling functions. Higher-level languages will hide this problem from you, but if you try doing this using the obvious method in your C program, you’ll quickly run into what’s known as the dangling pointer problem – you’re returning a pointer to a stack-dynamic variable that will no longer exist when the function exits, so the compiler will throw an error.

There are basically three ways you can solve this problem (that I know of anyway). The first is to create a heap-dynamic variable with malloc. Since the heap is not popped when a function exits, a variable declared this way will still be accessible to the calling function. The disadvantage to this method is that heap allocation and maintenance is very resource-intensive (and also requires the caller to explicitly free the memory when finished) and should be avoided if possible.

The second method is to declare the variable as static. This has the advantage of being simpler than heap allocation, but the disadvantage is that because it now refers to a location in the data segment (which has a static size, hence the name), there can only be one copy of this variable throughout the entire program, so if you try to declare multiple simultaneous variables with this method, they will all refer to the same location in memory. Don’t use static allocation if you plan on using multiple values declared with the same function at once.

In the interest of simplicity and flexibility I have chosen to simply declare my rational variable in the calling function and just use the callee to initialize its values. This has the advantage of encapsulating the numerator and denominator, making the individual fields of the rational type invisible to the programmer and freeing them from having to worry about implementation details.

Okay, now that we’ve gone through some of the nitty-gritty details of C programming, let’s continue implementing the rational type. We can make use of the rules of elementary algebra to add, subtract, multiply, and divide rationals as follows:


// Addition
void rat_add( rat_t *z, rat_t x, rat_t y ){
        z->n = x.n * y.d + x.d * y.n;
        z->d = x.d * y.d;
}

// Subtraction
void rat_sub( rat_t *z, rat_t x, rat_t y ){
        z->n = x.n * y.d - x.d * y.n;
        z->d = x.d * y.d;
}

// Multiplication
void rat_mul( rat_t *z, rat_t x, rat_t y ){
        z->n = x.n * y.n;
        z->d = x.d * y.d;
}

// Division
void rat_div( rat_t *z, rat_t x, rat_t y ){
        z->n = x.n * y.d;
        z->d = x.d * y.n;
}

The problem with using these functions alone is that with each successive application the numerator and denominator will both keep getting larger and larger. So in order to prevent the fractions from becoming too unwieldy, it helps to have a function to reduce the fraction to its lowest terms. For this we will use Euclid’s algorithm, which we know from elementary number theory. If you want to understand the code of this function, it might help to have a mathematical description of Euclid’s algorithm handy.


void rat_reduce( rat_t *z ){
        int r1 = z->n;
        int r2 = z->d;
        int gcd;
        while( r1 % r2 ){
                gcd = r1 % r2;
                r1 = r2;
                r2 = gcd;
        }
        z->n /= gcd;
        z->d /= gcd;
}

These are all the components needed to implement the rational type. We need a type definition, a way to initialize the type, implementations of all the arithmetic operators, and a function for reducing a rational type to its lowest terms.

The following is an example of our rational type in action. It is a Bayesian probability simulation that simulates pulling a die out of a bag of dice and then rolling it to get a number (here we ignore the properties of solid geometry and assume that we can have a platonic solid with any number of faces).

For those of you who aren’t familiar with Bayesian probability, basically what it does is it provides a method for computing conditional probability, that is, the probability of a certain event occurring given that another related event is known to have occurred. In this case the two conditional probabilities are (1) the probability that a given die was chosen, and (2) the probability that a given number was rolled. For example, if we have a six-sided die and a four-sided die, and we rolled a 5, the probability that we pulled out the four-sided die is 0 and the probability that we pulled out the six-sided die is 1. If we rolled a 3, the probability for both dice is 1/2.

This program takes as command line parameters the side numbers of all the dice and then prints out the conditional and unconditional probabilities of each die choice and roll result. To avoid redundancy, only the main function is shown…


int mainint argc, char **argv ){
        int dice[argc-1];
        int max = 0;
        forint i = 1; i < argc; i++ ){
                dice[i-1] = atoi( argv[i] );
                if( dice[i-1] > max ) max = dice[i-1];
        }
        printf"Number\t" );
        forint i = 0; i < argc-1; i++ ){
                printf"P(%d:%d)\t", i, dice[i] );
        }
        putchar'\n' );
        forint i = 1; i <= max; i++ ){
                printf"%3d\t", i );
                forint j = 0; j < argc-1; j++ ){
                        // P(i|j)
                        rat_t Pij;
                        rat_init( &Pij, (i<=dice[j])?1:0, dice[j] );
                        // P(i)
                        rat_t Pi;
                        rat_init( &Pi, 01 );
                        forint k = 0; k < argc-1; k++ ){
                                rat_t temp;
                                rat_init( &temp, 1, dice[j] / (argc-1) );
                                rat_add( &Pi, Pi, temp );
                        }
                        // P(j)
                        rat_t Pj;
                        rat_init( &Pj, 1, (argc-1) );
                        // P(j|i)
                        rat_t temp;
                        rat_mul( &temp, Pij, Pj );
                        rat_t Pji;
                        rat_div( &Pji, temp, Pi );
                        rat_reduce( &Pji );
                        // Print result
                        printf"%d/%d\t", Pji.n, Pji.d );
                }
                putchar'\n' );
        }
        return 0;
}

Basically all this program does is apply the standard formulas for classical and Bayesian probability to get all the conditional and unconditional probabilities for each event, represented by rational types. The applications of these formulas involve applying the rational operators we defined in accordance with those formulas. It’s a fairly simple program and not particularly imaginative, but it gets the point across of how these rational types can be used in practice.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s