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