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