Back to home page

LXR

 
 

    


0001 /*
0002  * rational fractions
0003  *
0004  * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
0005  *
0006  * helper functions when coping with rational numbers
0007  */
0008 
0009 #include <linux/rational.h>
0010 #include <linux/compiler.h>
0011 #include <linux/export.h>
0012 
0013 /*
0014  * calculate best rational approximation for a given fraction
0015  * taking into account restricted register size, e.g. to find
0016  * appropriate values for a pll with 5 bit denominator and
0017  * 8 bit numerator register fields, trying to set up with a
0018  * frequency ratio of 3.1415, one would say:
0019  *
0020  * rational_best_approximation(31415, 10000,
0021  *      (1 << 8) - 1, (1 << 5) - 1, &n, &d);
0022  *
0023  * you may look at given_numerator as a fixed point number,
0024  * with the fractional part size described in given_denominator.
0025  *
0026  * for theoretical background, see:
0027  * http://en.wikipedia.org/wiki/Continued_fraction
0028  */
0029 
0030 void rational_best_approximation(
0031     unsigned long given_numerator, unsigned long given_denominator,
0032     unsigned long max_numerator, unsigned long max_denominator,
0033     unsigned long *best_numerator, unsigned long *best_denominator)
0034 {
0035     unsigned long n, d, n0, d0, n1, d1;
0036     n = given_numerator;
0037     d = given_denominator;
0038     n0 = d1 = 0;
0039     n1 = d0 = 1;
0040     for (;;) {
0041         unsigned long t, a;
0042         if ((n1 > max_numerator) || (d1 > max_denominator)) {
0043             n1 = n0;
0044             d1 = d0;
0045             break;
0046         }
0047         if (d == 0)
0048             break;
0049         t = d;
0050         a = n / d;
0051         d = n % d;
0052         n = t;
0053         t = n0 + a * n1;
0054         n0 = n1;
0055         n1 = t;
0056         t = d0 + a * d1;
0057         d0 = d1;
0058         d1 = t;
0059     }
0060     *best_numerator = n1;
0061     *best_denominator = d1;
0062 }
0063 
0064 EXPORT_SYMBOL(rational_best_approximation);