## 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);
minerr = value;
printf ("Rational numbers close to %lf:\n", value);

// Read numerator/denominator limit from command line
if (argc > 2) limit = atoi(argv);

// 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).

This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.