fractions in c - a rational arithmetic library

chris (2008-11-09 00:19:17)
4177 views
2 replies
I got carried away today. After a brief IM conversation with a friend late last night, I went to bed with an urge to write this rational arithmetic library. With the baby asleep and the wife not looking, I set to work.. beer in hand.. and this is the result.

Interesting bits: using a struct typedef to pre-define the 'rational' datatype, also the use of recursion in the 'reduce' function to further reduce the fractional part of a rational number which has already been reduced from being top-heavy.

Caveats - this version doesn't play nice when values fall below zero - However, the latest update (scroll down the page to the second reply) does.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
	int integer;
	int numerator;
	int denominator;
} rational;

rational add ( rational *r, rational *r2 );
rational subtract ( rational *r, rational *r2 );
rational multiply ( rational *r, rational *r2);
rational divide ( rational *r, rational *r2);
rational reduce ( rational *r );
void display ( rational *r );

int main( int argc, char *argv[]){
	rational rational1, rational2, result;

	printf("nenter first numerator: ");
	scanf("%d", &rational1.numerator);
	printf("nenter first denominator: ");
	scanf("%d", &rational1.denominator);
	printf("nenter second numerator: ");
	scanf("%d", &rational2.numerator);
	printf("nenter second denominator: ");
	scanf("%d", &rational2.denominator);

	result = add( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nsum : ");
	display( &result);

	result = multiply( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nproduct : ");
	display( &result);

	result = subtract( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nsubtracted : ");
	display( &result);

	result = divide( &rational1, &rational2 );	
	result = reduce( &result );
	printf("ndivided : ");
	display( &result);

	printf("nn");
}

void display ( rational *pr ){
	if( pr->integer > 0 ){
		printf("%d ",pr->integer);
	}
	if( pr->numerator > 0 && pr->denominator > 0){
		printf("%d/%d",pr->numerator, pr->denominator);
	}
}

rational add ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 + nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational subtract ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 - nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational multiply ( rational *pr, rational *pr2 ){
	rational result;

	result.numerator = pr->numerator * pr2->numerator;
	result.denominator = pr->denominator * pr2->denominator;
	return result;
}


rational divide ( rational *pr, rational *pr2 ){
	rational result;

	result.numerator = pr->numerator * pr2->denominator;
	result.denominator = pr->denominator * pr2->numerator;
	return result;
}

rational reduce ( rational *pr ){
	int i;
	rational result, fraction, reduced;

	/* fraction is fractional part of a proper function. This will recurse to further reduce the fraction */

	if( pr->numerator > pr->denominator ){
		if( (pr->numerator % pr->denominator) ==0 ){
			/* this is a whole number */
			result.integer = pr->numerator / pr->denominator;
			result.numerator = 0;
			result.denominator = 0;
			return result;
		}
		result.integer = (int)(pr->numerator / pr->denominator);
		result.numerator = pr->numerator - (pr->denominator * result.integer);			
		result.denominator = pr->denominator;

		fraction.numerator = result.numerator;
		fraction.denominator = result.denominator;
		reduced = reduce (&fraction);

		result.numerator = reduced.numerator;	
		result.denominator = reduced.denominator;	

		return result;
	}else{
		if( pr->numerator == pr->denominator ){
			result.integer  = 1;
			result.numerator = 0;
			result.denominator = 0;
			return result;
		}
		i = pr->numerator;
		while(i>0){
			if(((pr->numerator % i) == 0 ) && ((pr->denominator %i ) == 0)){
				result.integer = 0;
				result.numerator = ( pr->numerator / i );
				result.denominator = ( pr->denominator / i );
				return result;
			}
			i--;
		}
		return result;
	}
}


christo
comment
chris
2008-11-09 22:06:01

Improving slightly with Euclidean algorithm

This version uses the Euclidean algorithm to figure out the highest common factor in the reduce process.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
	int integer;
	int numerator;
	int denominator;
} rational;

rational add ( rational *r, rational *r2 );
rational subtract ( rational *r, rational *r2 );
rational multiply ( rational *r, rational *r2);
rational divide ( rational *r, rational *r2);
rational reduce ( rational *r );
void display ( rational *r );
int hcf ( int, int );

int main( int argc, char *argv[]){
	rational rational1, rational2, result;

	printf("nenter first numerator: ");
	scanf("%d", &rational1.numerator);
	printf("nenter first denominator: ");
	scanf("%d", &rational1.denominator);
	printf("nenter second numerator: ");
	scanf("%d", &rational2.numerator);
	printf("nenter second denominator: ");
	scanf("%d", &rational2.denominator);

	result = add( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nsum : ");
	display( &result);

	result = multiply( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nproduct : ");
	display( &result);

	result = subtract( &rational1, &rational2 );	
	result = reduce( &result );
	printf("nsubtracted : ");
	display( &result);

	result = divide( &rational1, &rational2 );	
	result = reduce( &result );
	printf("ndivided : ");
	display( &result);

	printf("nn");
}

void display ( rational *pr ){
	if( pr->integer > 0 ){
		printf("%d ",pr->integer);
	}
	if( pr->numerator > 0 && pr->denominator > 0){
		printf("%d/%d",pr->numerator, pr->denominator);
	}
}

rational add ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 + nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational subtract ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 - nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational multiply ( rational *pr, rational *pr2 ){
	rational result;

	result.numerator = pr->numerator * pr2->numerator;
	result.denominator = pr->denominator * pr2->denominator;
	return result;
}


rational divide ( rational *pr, rational *pr2 ){
	rational result;

	result.numerator = pr->numerator * pr2->denominator;
	result.denominator = pr->denominator * pr2->numerator;
	return result;
}

rational reduce ( rational *pr ){
	int i;
	rational result, fraction, reduced;

	/* fraction is fractional part of a proper function. This will recurse to further reduce the fraction */

	if( pr->numerator > pr->denominator ){
		if( (pr->numerator % pr->denominator) ==0 ){
			/* this is a whole number */
			result.integer = pr->numerator / pr->denominator;
			result.numerator = 0;
			result.denominator = 0;
			return result;
		}
		result.integer = (int)(pr->numerator / pr->denominator);
		result.numerator = pr->numerator - (pr->denominator * result.integer);			
		result.denominator = pr->denominator;

		fraction.numerator = result.numerator;
		fraction.denominator = result.denominator;
		reduced = reduce (&fraction);

		result.numerator = reduced.numerator;	
		result.denominator = reduced.denominator;	

		return result;
	}else{
		if( pr->numerator == pr->denominator ){
			result.integer  = 1;
			result.numerator = 0;
			result.denominator = 0;
			return result;
		}

		i = hcf( pr->numerator, pr->denominator );
	
		result.integer = 0;
		result.numerator = ( pr->numerator / i );
		result.denominator = ( pr->denominator / i );
		return result;
	}
}

int hcf(int i, int j) {
	if( j == 0 ){
		return i;
	}else{
		hcf(j, i % j);
	}
}

christo
reply icon
chris
2008-11-27 08:34:08

fixed negative number issues

It was annoying me, so I have fixed the issues with negative numbers, which sometimes occur as a result of the subtract() function. This version is very solid. Next iteration, I will allow the user to provide the integer part, allowing proper fractions > 1.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct {
	int integer;
	int numerator;
	int denominator;
} rational;

rational add ( rational *r, rational *r2 );
rational subtract ( rational *r, rational *r2 );
rational multiply ( rational *r, rational *r2);
rational divide ( rational *r, rational *r2);
rational reduce ( rational *r );
void display ( rational *r );
int hcf ( int, int );

int main( int argc, char *argv[]){
	rational rational1, rational2, result;

	printf("\nenter first numerator: ");
	scanf("%d", &rational1.numerator);
	printf("\nenter first denominator: ");
	scanf("%d", &rational1.denominator);
	printf("\nenter second numerator: ");
	scanf("%d", &rational2.numerator);
	printf("\nenter second denominator: ");
	scanf("%d", &rational2.denominator);

	result = add( &rational1, &rational2 );	
	result = reduce( &result );
	printf("\nsum : ");
	display( &result);

	result = multiply( &rational1, &rational2 );	
	result = reduce( &result );
	printf("\nproduct : ");
	display( &result);

	result = subtract( &rational1, &rational2 );	
	result = reduce( &result );
	printf("\nsubtracted : ");
	display( &result);

	result = divide( &rational1, &rational2 );	
	result = reduce( &result );
	printf("\ndivided : ");
	display( &result);

	printf("\n\n");
}

void display ( rational *pr ){

	if( pr->integer > 0 ){
		printf("%d ",pr->integer);
	}

	if( pr->numerator < 0 || pr->denominator < 0){
		if(pr->numerator < 0){
			pr->numerator *= -1;
		}
		if(pr->denominator < 0){
			pr->denominator *= -1;
		}
		printf("-");
	}
	printf("%d/%d",pr->numerator, pr->denominator);
}

rational add ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	result.integer = 0;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 + nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational subtract ( rational *pr, rational *pr2 ){
	rational result;
	int hcd; 
	int nom1, nom2, tot;

	hcd = pr->denominator * pr2->denominator;
	nom1 = pr2->denominator * pr->numerator;
	nom2 = pr->denominator * pr2->numerator;
	tot = nom1 - nom2;

	result.numerator = tot;
	result.denominator = hcd;
	return result;
}

rational multiply ( rational *pr, rational *pr2 ){
	rational result;
	
	result.numerator = pr->numerator * pr2->numerator;
	result.denominator = pr->denominator * pr2->denominator;
	return result;
}


rational divide ( rational *pr, rational *pr2 ){
	rational result;

	result.numerator = pr->numerator * pr2->denominator;
	result.denominator = pr->denominator * pr2->numerator;
	return result;
}

rational reduce ( rational *pr ){
	int i, neg;
	rational result, fraction, reduced, returnresult;

	/* set a flag if there is a -ve component */
	neg = 0;
	if( pr->integer < 0 || pr->numerator < 0 || pr->denominator < 0 ){
		neg = 1;
	}

	/* set all components to their positive magnitude */
	pr->integer = (pr->integer < 0) ? pr->integer * -1 : pr->integer;
	pr->numerator = (pr->numerator < 0) ? pr->numerator * -1 : pr->numerator;
	pr->denominator = (pr->denominator < 0) ? pr->denominator * -1 : pr->denominator;

	/* fraction is fractional part of a proper function. This will recurse to further reduce the fraction */
	/* should test magnitude not difference */
	if( pr->numerator > pr->denominator ){
		if( (pr->numerator % pr->denominator) ==0 ){
			/* this is a whole number */
			result.integer = pr->numerator / pr->denominator;
			result.numerator = 0;
			result.denominator = 0;
			returnresult =  result;
		}else{
			result.integer = (int)(pr->numerator / pr->denominator);
			result.numerator = pr->numerator - (pr->denominator * result.integer);			
			result.denominator = pr->denominator;

			fraction.integer = result.integer;
			fraction.numerator = result.numerator;
			fraction.denominator = result.denominator;
			reduced = reduce (&fraction);

			result.numerator = reduced.numerator;	
			result.denominator = reduced.denominator;	

			returnresult = result;
		}
	}else{
		if( pr->numerator == pr->denominator ){
			result.integer  = 1;
			result.numerator = 0;
			result.denominator = 0;
			returnresult = result;
		}

		i = hcf( pr->numerator, pr->denominator );
	
		result.integer = 0;
		result.numerator = ( pr->numerator / i );
		result.denominator = ( pr->denominator / i );
		returnresult =  result;
	}
	/* before returning, negate if necessary */
	if( neg == 1 ){
		if( returnresult.integer > 0 ){
			returnresult.integer *= -1;
		}else{
			returnresult.numerator *= -1;
		}
	}
	return returnresult;
}

int hcf(int i, int j) {
	if( j == 0 ){
		return i;
	}else{
		hcf(j, i % j);
	}
}
reply icon