The Rational Number Class in C

This note describes how facilities for manipulating rational numbers might be built in the C programming language. This note should be read in conjunction with the notes onclasses and methods in Java.

The first version is modelled very closely on the Java example in the notes described above.

Compilation of C code

A C programme that does anything at all complex is likely to constructed from several separate compilation units that contain executable code and data definitions. These will, conventionally, be files with names ending in ".c". In order for data and code definitions that are included in a particular compilation to be publically visible, there will also be a header file that contains basic information about variable names and functions. These will, conventionally, be files with names ending in ".h" that are "included" in the compilation units.

The C compilation units are broadly equivalent to Java ".java" files. Java has no equivalent to C's header files, instead a Java compiler gets the information it requires by directly examining the ".java" source code files.

C compilation generates object files (with names ending in ".o") and these are then linked along with standard libraries to form an executable file.

On Unix/Linux platforms the command to compile C programmes is commonly gcc and dependencies between the various source files is handled via a makefile. The makefile used for the first of these examples is shown below.

ratarray :	ratarray.o ratclass.o
	gcc -g  -o ratarray ratarray.o ratclass.o

ratarray.o :	ratarray.c ratnum.h
	gcc -g  -c ratarray.c

ratclass.o :	ratclass.c ratnum.h
	gcc -g  -c ratclass.c

The developer will create the executable file ratarray by simply typing

make ratarray

at the command prompt. The make file consists of three dependencies indicating that, for example, the file ratarray depends on the files ratarray.o and ratclass.o, in turn ratclass.o depends on ratclass.c and ratnum.h. The make command examines the operating system time stamps on the files to see whether any files depend on files that have been modified more recently, if so the make command issues the appropriate compilation commands.

The Java compiler javac handles most of the dependency issues directly.

Example 1

This first example of rational number handling in C is closely modelled on the Java version.

First here is the header file ratnum.h.

struct	ratnum
{
	long	int	num;
	long	int	den;
};

typedef	struct	ratnum	* ratref;

ratref	newrat(long int,long int);
void	showrat(ratref);
ratref	addrat(ratref,ratref);
ratref	addinttorat(ratref,long int);
int	ratcomp(ratref *,ratref *);

This defines a data structure ratnum that will be available in any compilation unit that includes this header file. In practice, inspired by the Java code, nearly all uses will involve a pointer or reference to such a structure, the abbreviated notation ratref is equivalent to writing struct ratnum *.

A number of methods (or functions) are defined. These are C function prototypes that define the number and types of arguments and return values.

The compilation unit ratclass.c includes all the standard functions for manipulating rational numbers. Here's the code.

#include	<stdio.h>
#include	"ratnum.h"

static	ratref simplify(ratref);
static	long int euclid(long int, long int);

ratref	newrat(long int num, long int den)
{
	long int	a,b;
	ratref	r;
	r = (ratref)calloc(sizeof(struct ratnum));
	r->num = num;
	r->den = den;
	return simplify(r);
}

void	showrat(ratref x)
{
	double	rr;
	rr = (double)(x->num)/(double)(x->den);
	fprintf(stderr,"%ld/",x->num);
	fprintf(stderr,"%ld",x->den);
	fprintf(stderr," (%20.10lf)\n",rr);
}

ratref	addrat(ratref a, ratref b)
{
	ratref	r;
	r = simplify(newrat(a->num*b->den + b->num*a->den,a->den*b->den));
	return r;
}

ratref	addinttorat(ratref a,long int x)
{
	return simplify(newrat(a->num + x * a->den, a->den));
}

static	ratref	simplify(ratref a)
{
	long int	gcd;
	gcd = euclid(a->num,a->den);
	a->num /= gcd;
	a->den /= gcd;
	return a;
}

static	long int	euclid(long int a, long int b)
{
	if(b==0)	return a;
	else		return euclid(b,a%b);
}

int	ratcomp(ratref *a, ratref *b)
{
	int	rv;
	rv =  (*a)->den*(*b)->num - (*a)->num*(*b)->den;
	return rv;
}

For details of the algorithms etc., see the Java example. It will be noticed that two of the functions (simplfy() and euclid()) are not mentioned in ratnum.h and have the C keyword static in front of their definitions. These are, effectively, private functions for use within ratclass.c. Note that they still have to have prototypes and these appear at the start of ratclass.c. The final function (ratcomp()) is a comparator function that will be used when an array of rational numbers is sorted.

The code in ratarray.c uses these functions to create an array of rational numbers, display them, sort them and then display them again. Here's the code.

#include	<stdio.h>
#include	"ratnum.h"

main()
{
	int 	i,j;
	ratref	nums[10];
	for(i=0;i<10;i++)
	{
		j = i%3;
		nums[i] = newrat((long int)(j+3),(long int)(i+6));
	}
	for(i=0;i<10;i++)
	{
		showrat(nums[i]);
	}
	qsort(nums,10,sizeof(ratref),ratcomp);
	fprintf(stderr,"Sorted array\n");
	for(i=0;i<10;i++)
	{
		showrat(nums[i]);
	}
	
}

There are a number of interesting points here. Note that slightly different syntax of the two include lines, the first refers to a standard library header file and the second to the specific header for the rational numbers functions. The effect is that the compiler looks in different places for the header files.

The array nums[] contains not rational numbers but references (pointers) to rational numbers, the function newrat() obtains sufficient memory from a system pool using the standard C library function calloc() and returns the address of the allocated area. This is entirely analogous to the operation the Java version.

The standard C library function qsort() is used to sort the array. This is a generic sorting function, the four parameters are

  1. Base Address

    This is the start address of the array to be sorted. Strictly C does not have arrays, this is simply the start address of the block of data.

  2. Number of elements

  3. Size of element

    sizeof is a standard C operator whose value is the amount of memory occupied by the parameter. In conjunction with the base address and the number of elements this enables the sort routine to "walk" the array.

  4. Comparator Function

    This is the name of (in effect a pointer to) a function that will compare two objects and return a -ve or +ve value depending on how they should be ordered. In C a "stand-alone" function name is interpreted as a pointer to the function (i.e. the start address of the code of the function).

    Formally the parameters of this function will be of type void *, this slightly odd notation is C's way of indicating a generic pointer roughly equivalent to Java's Object class.

    In C conversion of generic pointers to specific types does not require explicit casting unlike Java.

Apart from a slightly different way of displaying floating point values the C output is exactly the same as the Java output.

1/2 (        0.5000000000)
4/7 (        0.5714285714)
5/8 (        0.6250000000)
1/3 (        0.3333333333)
2/5 (        0.4000000000)
5/11 (        0.4545454545)
1/4 (        0.2500000000)
4/13 (        0.3076923077)
5/14 (        0.3571428571)
1/5 (        0.2000000000)
Sorted array
5/8 (        0.6250000000)
4/7 (        0.5714285714)
1/2 (        0.5000000000)
5/11 (        0.4545454545)
2/5 (        0.4000000000)
5/14 (        0.3571428571)
1/3 (        0.3333333333)
4/13 (        0.3076923077)
1/4 (        0.2500000000)
1/5 (        0.2000000000)

There are a number of differences from the Java example that are worth noting.

  1. The explicit use of the memory allocation function calloc() in the newrat() function.

  2. The generic sorting function is significantly easier to use in C. This is partly because Java seems to lack the notion of pointer (or reference) to function and has to work via a clumsy and unnecessary intermediate class.

  3. There is no facility in the C programme to release the memory associated with a rational number once it is no longer required. In Java the garbage collector handles this issues automatically.

Whether this C programme can be described as object-oriented is left for the reader to decide.

Example 2

This example shows the same fucntionality as the previous example only it uses a more traditional C style in which the programme works with rational numbers rather pointers (or references) to rational numbers. It is based on and derived from the previous example, the compilation unit previously called ratclass.c is now called ratlib.c to reflect the fact that the sort of general purpose support code included in the unit would normally be placed in a library file and the functions in the code would be linked into an executable programme as required, this is not done here.

The header file ratnum.h now looks rather different.

struct	ratnumber
{
	long	int	num;
	long	int	den;
};

typedef	struct ratnumber ratnum;

ratnum	mkrat(long int,long int);
ratnum	addrat(ratnum,ratnum);
ratnum	addinttorat(ratnum,long int);
void	showrat(ratnum);
int	ratcomp(ratnum*,ratnum *);

The differences are little more than replacing ratref by ratnum although the absence of the pointer indicating symbol * on the typedef should be noted.

The compilation unit ratlib.c shows rather greater differences. Here is the code.

#include	<stdio.h>
#include	"ratnum.h"

static	void simplify(ratnum *);
static	long int euclid(long int, long int);


ratnum	mkrat(long int a, long int b)
{
	ratnum r;
	r.num = a;
	r.den = b;
	simplify(&r);
	return r;
}

void	showrat(ratnum x)
{
	double	rr;
	rr = (double)(x.num)/(double)(x.den);
	fprintf(stderr,"%ld/",x.num);
	fprintf(stderr,"%ld",x.den);
	fprintf(stderr," (%20.10lf)\n",rr);
}

ratnum	addrat(ratnum a, ratnum b)
{
	ratnum	r;
	r.num = a.num*b.den + b.num*a.den;
	r.den = a.den*b.den;
	simplify(&r);
	return r;
}

ratnum	addinttorat(ratnum a,long int x)
{
	ratnum sum;
	sum.num = a.num + x*a.den;
	sum.den = a.den;
	simplify(&sum); 
	return sum;
}

static	void	simplify(ratnum *a)
{
	long int	gcd;
	gcd = euclid(a->num,a->den);
	a->num /= gcd;
	a->den /= gcd;
}

static	long int	euclid(long int a, long int b)
{
	if(b==0)	return a;
	else		return euclid(b,a%b);
}

int	ratcomp(ratnum *a, ratnum *b)
{
	return  a->den*b->num - a->num*b->den;
}

Several of the functions have the return value type ratnum and have a local internal variable of type ratnum whose value is returned by the function. On exit from the function the storage associated with the local variable is released.

The difference between newrat() in the previous example and mkrat() in the current example is worthy of more detaile explanation. The function newrat() obtained storage for a rational number from system memory using the library function calloc(), this is called dynamic memory allocation and suffers from two problems, namely. significant overheads in maintaining the dynamic memory system and the problem of recovering the memory when it is no longer required. The mkrat() function simply returns the value of the rational number via the standard function return mechanism, it is then the responsibility of the code that called mkrat() to save the returned value, usually via assignment of the returned functional value to a local variable.

Note also that the "private" function simplify() does not return any value (its type is void) but operates on the rational number supplied as parameter. To make this work it is necessary to supply the address of the rational number that is to be simplified since C functional parameter transfer involves the function making a copy of the value of a parameter. In this case it is the address of the variable that is copied and used within the function to provide "remote access" to the actual data.

Notice also that the ratcomp() function required by the library function qsort() now takes pointers to rational numbers as parameters rather than pointers to pointers.

There are two minor changes to the programme ratarray.c; ratref is replaced by ratnum and the call to newrat() is replaced by a call to mkrat(). Here is the code.

#include	<stdio.h>
#include	"ratnum.h"

main()
{
	int 	i,j;
	ratnum	nums[10];
	for(i=0;i<10;i++)
	{
		j = i%3;
		nums[i] = mkrat((long int)(j+3),(long int)(i+6));
	}
	for(i=0;i<10;i++)
	{
		showrat(nums[i]);
	}
	qsort(nums,10,sizeof(ratnum),ratcomp);
	fprintf(stderr,"Sorted array\n");
	for(i=0;i<10;i++)
	{
		showrat(nums[i]);
	}
	
}

It produced exactly the same output.


This page is part of a set of notes about the Java programming language prepared by Peter Burden for the module CP4044.