rational.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10

    1 /*
    2  * rational fractions
    3  *
    4  * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
    5  *
    6  * helper functions when coping with rational numbers
    7  */
    8 
    9 #include <linux/rational.h>
   10 #include <linux/compiler.h>
   11 #include <linux/export.h>
   12 
   13 /*
   14  * calculate best rational approximation for a given fraction
   15  * taking into account restricted register size, e.g. to find
   16  * appropriate values for a pll with 5 bit denominator and
   17  * 8 bit numerator register fields, trying to set up with a
   18  * frequency ratio of 3.1415, one would say:
   19  *
   20  * rational_best_approximation(31415, 10000,
   21  *              (1 << 8) - 1, (1 << 5) - 1, &n, &d);
   22  *
   23  * you may look at given_numerator as a fixed point number,
   24  * with the fractional part size described in given_denominator.
   25  *
   26  * for theoretical background, see:
   27  * http://en.wikipedia.org/wiki/Continued_fraction
   28  */
   29 
   30 void rational_best_approximation(
   31         unsigned long given_numerator, unsigned long given_denominator,
   32         unsigned long max_numerator, unsigned long max_denominator,
   33         unsigned long *best_numerator, unsigned long *best_denominator)
   34 {
   35         unsigned long n, d, n0, d0, n1, d1;
   36         n = given_numerator;
   37         d = given_denominator;
   38         n0 = d1 = 0;
   39         n1 = d0 = 1;
   40         for (;;) {
   41                 unsigned long t, a;
   42                 if ((n1 > max_numerator) || (d1 > max_denominator)) {
   43                         n1 = n0;
   44                         d1 = d0;
   45                         break;
   46                 }
   47                 if (d == 0)
   48                         break;
   49                 t = d;
   50                 a = n / d;
   51                 d = n % d;
   52                 n = t;
   53                 t = n0 + a * n1;
   54                 n0 = n1;
   55                 n1 = t;
   56                 t = d0 + a * d1;
   57                 d0 = d1;
   58                 d1 = t;
   59         }
   60         *best_numerator = n1;
   61         *best_denominator = d1;
   62 }
   63 
   64 EXPORT_SYMBOL(rational_best_approximation);

Cache object: e1ee53b88a3e86b69c712aec0885ebf7

[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.

FreeBSD/Linux Kernel Cross Reference sys/lib/rational.c

FreeBSD/Linux Kernel Cross Reference
sys/lib/rational.c