Rational Hunt: Finding a rational approximation to a value

Earlier this afternoon, I was trying to work out why the internal fast RC oscillator in every dsPIC microcontroller (well, every one I’ve used) has a frequency of 7.37MHz. It turns out that it’s because it facilitates the convenient production of standard baud rates like 38400, 115200, etc. However, once I started thinking about it, I wanted to find out if there was a good rational approximation to 7.37 that would let me configure the dsPIC’s pre- and post-scalers to produce a convenient round figure for Fosc. By “rational approximation”, I mean a fraction that’s close in value to 7.37, but with integer values for its numerator and denominator.

So, instead of just googling it (the “rational” thing to do – sorry!), I wrote a C program to search for rational approximations for arbitrary values. Here’s the code:

//
// rationalhunt.c - Find rational number close to a value
// written by Ted Burke
// last updated 17-11-2012
//
// To compile with MinGW:
//
//		gcc -o rationalhunt.exe rationalhunt.c
//
// To run (e.g. find a rational approximation to 7.37 with
// numerator and denominator less than 100):
//
//		rationalunt 7.3728 100
//

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

int main(int argc, char* argv[])
{
	// Variables
	double value, r, minerr;
	int n=1,d=1, best_n=1, best_d=1, limit=1000;
	
	// Check that a target value was provided
	if (argc < 2)
	{
		printf("Usage: rationalhunt POSITIVE_VALUE\n");
		return 1;
	}
	
	// Read target value from command line
	value = atof(argv[1]);
	minerr = value;
	printf ("Rational numbers close to %lf:\n", value);
	
	// Read numerator/denominator limit from command line
	if (argc > 2) limit = atoi(argv[2]);
	
	// Zig-zag back and forth, above and below target
	while(1)
	{
		// Increment numerator until target is exceeded
		while(n/(double)d <= value && n < limit) ++n;
		if (n >= limit) break;
		
		r = (n-1)/(double)d;
		if (fabs(r - value) < fabs(minerr)) {minerr = r - value; best_n = n-1; best_d = d;}
		printf("%d/%d = %lf ,   error = %lf\n", (n-1), d, r, r - value);

		r = n/(double)d;
		if (fabs(r - value) < fabs(minerr)) {minerr = r - value; best_n = n; best_d = d;}
		printf("%d/%d = %lf ,   error = %lf\n", n, d, r, r - value);
		
		// Increment denominator until target is no longer exceeded
		while(n/(double)d > value && d < limit) ++d;
		if (d >= limit) break;
		
		r = n/(double)(d-1);
		if (fabs(r - value) < fabs(minerr)) {minerr = r - value; best_n = n; best_d = d-1;}
		printf("%d/%d = %lf ,   error = %lf\n", n, (d-1), r, r - value);

		r = n/(double)d;
		if (fabs(r - value) < fabs(minerr)) {minerr = r - value; best_n = n; best_d = d;}
		printf("%d/%d = %lf ,   error = %lf\n", n, d, r, r - value);		
	}

	// Print out best match
	r = best_n/(double)(best_d);
	printf("\nMinimum error: %d/%d = %lf ,   error = %lf\n", best_n, best_d, r, r - value);
	
	return 0;
}

Here’s how it looked when I compiled and ran it:

If you relax the limit on the size of the numerator and denominator (I specified 1000 this time), it finds an even better match:

So, as it turned out, 59/8 and 811/110 are both good approximations to 7.3728 (apparently 7.37MHz is itself an approximation to 7372800Hz).