1*4882a593Smuzhiyun // SPDX-License-Identifier: GPL-2.0
2*4882a593Smuzhiyun /*
3*4882a593Smuzhiyun * rational fractions
4*4882a593Smuzhiyun *
5*4882a593Smuzhiyun * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <oskar@scara.com>
6*4882a593Smuzhiyun * Copyright (C) 2019 Trent Piepho <tpiepho@gmail.com>
7*4882a593Smuzhiyun *
8*4882a593Smuzhiyun * helper functions when coping with rational numbers
9*4882a593Smuzhiyun */
10*4882a593Smuzhiyun
11*4882a593Smuzhiyun #include <linux/rational.h>
12*4882a593Smuzhiyun #include <linux/compiler.h>
13*4882a593Smuzhiyun #include <linux/kernel.h>
14*4882a593Smuzhiyun
15*4882a593Smuzhiyun /*
16*4882a593Smuzhiyun * calculate best rational approximation for a given fraction
17*4882a593Smuzhiyun * taking into account restricted register size, e.g. to find
18*4882a593Smuzhiyun * appropriate values for a pll with 5 bit denominator and
19*4882a593Smuzhiyun * 8 bit numerator register fields, trying to set up with a
20*4882a593Smuzhiyun * frequency ratio of 3.1415, one would say:
21*4882a593Smuzhiyun *
22*4882a593Smuzhiyun * rational_best_approximation(31415, 10000,
23*4882a593Smuzhiyun * (1 << 8) - 1, (1 << 5) - 1, &n, &d);
24*4882a593Smuzhiyun *
25*4882a593Smuzhiyun * you may look at given_numerator as a fixed point number,
26*4882a593Smuzhiyun * with the fractional part size described in given_denominator.
27*4882a593Smuzhiyun *
28*4882a593Smuzhiyun * for theoretical background, see:
29*4882a593Smuzhiyun * http://en.wikipedia.org/wiki/Continued_fraction
30*4882a593Smuzhiyun */
31*4882a593Smuzhiyun
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)32*4882a593Smuzhiyun void rational_best_approximation(
33*4882a593Smuzhiyun unsigned long given_numerator, unsigned long given_denominator,
34*4882a593Smuzhiyun unsigned long max_numerator, unsigned long max_denominator,
35*4882a593Smuzhiyun unsigned long *best_numerator, unsigned long *best_denominator)
36*4882a593Smuzhiyun {
37*4882a593Smuzhiyun /* n/d is the starting rational, which is continually
38*4882a593Smuzhiyun * decreased each iteration using the Euclidean algorithm.
39*4882a593Smuzhiyun *
40*4882a593Smuzhiyun * dp is the value of d from the prior iteration.
41*4882a593Smuzhiyun *
42*4882a593Smuzhiyun * n2/d2, n1/d1, and n0/d0 are our successively more accurate
43*4882a593Smuzhiyun * approximations of the rational. They are, respectively,
44*4882a593Smuzhiyun * the current, previous, and two prior iterations of it.
45*4882a593Smuzhiyun *
46*4882a593Smuzhiyun * a is current term of the continued fraction.
47*4882a593Smuzhiyun */
48*4882a593Smuzhiyun unsigned long n, d, n0, d0, n1, d1, n2, d2;
49*4882a593Smuzhiyun n = given_numerator;
50*4882a593Smuzhiyun d = given_denominator;
51*4882a593Smuzhiyun n0 = d1 = 0;
52*4882a593Smuzhiyun n1 = d0 = 1;
53*4882a593Smuzhiyun
54*4882a593Smuzhiyun for (;;) {
55*4882a593Smuzhiyun unsigned long dp, a;
56*4882a593Smuzhiyun
57*4882a593Smuzhiyun if (d == 0)
58*4882a593Smuzhiyun break;
59*4882a593Smuzhiyun /* Find next term in continued fraction, 'a', via
60*4882a593Smuzhiyun * Euclidean algorithm.
61*4882a593Smuzhiyun */
62*4882a593Smuzhiyun dp = d;
63*4882a593Smuzhiyun a = n / d;
64*4882a593Smuzhiyun d = n % d;
65*4882a593Smuzhiyun n = dp;
66*4882a593Smuzhiyun
67*4882a593Smuzhiyun /* Calculate the current rational approximation (aka
68*4882a593Smuzhiyun * convergent), n2/d2, using the term just found and
69*4882a593Smuzhiyun * the two prior approximations.
70*4882a593Smuzhiyun */
71*4882a593Smuzhiyun n2 = n0 + a * n1;
72*4882a593Smuzhiyun d2 = d0 + a * d1;
73*4882a593Smuzhiyun
74*4882a593Smuzhiyun /* If the current convergent exceeds the maxes, then
75*4882a593Smuzhiyun * return either the previous convergent or the
76*4882a593Smuzhiyun * largest semi-convergent, the final term of which is
77*4882a593Smuzhiyun * found below as 't'.
78*4882a593Smuzhiyun */
79*4882a593Smuzhiyun if ((n2 > max_numerator) || (d2 > max_denominator)) {
80*4882a593Smuzhiyun unsigned long t = min((max_numerator - n0) / n1,
81*4882a593Smuzhiyun (max_denominator - d0) / d1);
82*4882a593Smuzhiyun
83*4882a593Smuzhiyun /* This tests if the semi-convergent is closer
84*4882a593Smuzhiyun * than the previous convergent.
85*4882a593Smuzhiyun */
86*4882a593Smuzhiyun if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) {
87*4882a593Smuzhiyun n1 = n0 + t * n1;
88*4882a593Smuzhiyun d1 = d0 + t * d1;
89*4882a593Smuzhiyun }
90*4882a593Smuzhiyun break;
91*4882a593Smuzhiyun }
92*4882a593Smuzhiyun n0 = n1;
93*4882a593Smuzhiyun n1 = n2;
94*4882a593Smuzhiyun d0 = d1;
95*4882a593Smuzhiyun d1 = d2;
96*4882a593Smuzhiyun }
97*4882a593Smuzhiyun *best_numerator = n1;
98*4882a593Smuzhiyun *best_denominator = d1;
99*4882a593Smuzhiyun }
100