Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

65 lines (60 sloc) 1.555 kb
/*
* rational fractions
*
* Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
*
* helper functions when coping with rational numbers
*/
#include <linux/rational.h>
#include <linux/compiler.h>
#include <linux/export.h>
/*
* calculate best rational approximation for a given fraction
* taking into account restricted register size, e.g. to find
* appropriate values for a pll with 5 bit denominator and
* 8 bit numerator register fields, trying to set up with a
* frequency ratio of 3.1415, one would say:
*
* rational_best_approximation(31415, 10000,
* (1 << 8) - 1, (1 << 5) - 1, &n, &d);
*
* you may look at given_numerator as a fixed point number,
* with the fractional part size described in given_denominator.
*
* for theoretical background, see:
* http://en.wikipedia.org/wiki/Continued_fraction
*/
void rational_best_approximation(
unsigned long given_numerator, unsigned long given_denominator,
unsigned long max_numerator, unsigned long max_denominator,
unsigned long *best_numerator, unsigned long *best_denominator)
{
unsigned long n, d, n0, d0, n1, d1;
n = given_numerator;
d = given_denominator;
n0 = d1 = 0;
n1 = d0 = 1;
for (;;) {
unsigned long t, a;
if ((n1 > max_numerator) || (d1 > max_denominator)) {
n1 = n0;
d1 = d0;
break;
}
if (d == 0)
break;
t = d;
a = n / d;
d = n % d;
n = t;
t = n0 + a * n1;
n0 = n1;
n1 = t;
t = d0 + a * d1;
d0 = d1;
d1 = t;
}
*best_numerator = n1;
*best_denominator = d1;
}
EXPORT_SYMBOL(rational_best_approximation);
Jump to Line
Something went wrong with that request. Please try again.