lib: Fix possible incorrect result from rational fractions helper
PATCH 1/1 lib: Fix possible incorrect result from rational fractions helper
In some cases the previous algorithm would not return the closest approximation. This would happen when a semi-convergent was the closest, as the previous algorithm would only consider convergents.
As an example, consider an initial value of 5/4, and trying to find the closest approximation with a maximum of 4 for numerator and denominator. The previous algorithm would return 1/1 as the closest approximation, while this version will return the correct answer of 4/3.
To do this, the main loop performs effectively the same operations as it did before. It must now keep track of the last three approximations, n2/d2 .. n0/d0, while before it only needed the last two.
If an exact answer is not found, the algorithm will now calculate the best semi-convergent term, t, which is a single expression with two divisions:
min((max_numerator - n0) / n1, (max_denominator - d0) / d1)
This will be used if it is better than previous convergent. The test for this is generally a simple comparison, 2*t > a. But in an edge case, where the convergent's final term is even and the best allowable semi-convergent has a final term of exactly half the convergent's final term, the more complex comparison (d0*dp > d1*d) is used.
I also wrote some comments explaining the code. While one still needs to look up the math elsewhere, they should help a lot to follow how the code relates to that math.
--- lib/rational.c | 63 +++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 50 insertions(+), 13 deletions(-)
lib/rational.c +50 -13
@@ -3,6 +3,7 @@* rational fractions * * Copyright (C) 2009 emlix GmbH, Oskar Schirmer <[email protected]> +* Copyright (C) 2019 Trent Piepho <[email protected]> * * helper functions when coping with rational numbers */
@@ -10,6 +11,7 @@#include <linux/rational.h> #include <linux/compiler.h> #include <linux/export.h> +#include <linux/kernel.h> /* * calculate best rational approximation for a given fraction
@@ -33,30 +35,65 @@ void rational_best_approximation( unsigned long max_numerator, unsigned long max_denominator, unsigned long *best_numerator, unsigned long *best_denominator) { - unsigned long n, d, n0, d0, n1, d1; +/* n/d is the starting rational, which is continually +* decreased each iteration using the Euclidean algorithm. +* +* dp is the value of d from the prior iteration. +* +* n2/d2, n1/d1, and n0/d0 are our successively more accurate +* approximations of the rational. They are, respectively, +* the current, previous, and two prior iterations of it. +* +* a is current term of the continued fraction. +*/ +unsigned long n, d, n0, d0, n1, d1, n2, d2; n = given_numerator; d = given_denominator; n0 = d1 =0 ; n1 = d0 =1 ; +for (;;) { -unsigned long t, a; -if ((n1 > max_numerator) || (d1 > max_denominator)) { - n1 = n0; - d1 = d0; -break ; - } +unsigned long dp, a; +if (d ==0 )break ; - t = d; +/* Find next term in continued fraction, 'a', via +* Euclidean algorithm. +*/ + dp = d; a = n / d; d = n % d; - n = t; - t = n0 + a * n1; + n = dp; + +/* Calculate the current rational approximation (aka +* convergent), n2/d2, using the term just found and +* the two prior approximations. +*/ + n2 = n0 + a * n1; + d2 = d0 + a * d1; + +/* If the current convergent exceeds the maxes, then +* return either the previous convergent or the +* largest semi-convergent, the final term of which is +* found below as 't'. +*/ +if ((n2 > max_numerator) || (d2 > max_denominator)) { +unsigned long t =min ((max_numerator - n0) / n1, + (max_denominator - d0) / d1); + +/* This tests if the semi-convergent is closer +* than the previous convergent. +*/ +if (2u * t > a || (2u * t == a && d0 * dp > d1 * d)) { + n1 = n0 + t * n1; + d1 = d0 + t * d1; + } +break ; + } n0 = n1; - n1 = t; - t = d0 + a * d1; + n1 = n2; d0 = d1; - d1 = t; + d1 = d2; } *best_numerator = n1; *best_denominator = d1;
Signature · 1 line
2.20.1
Andrew Morton
maintainerQuoted 24 lines · On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <[email protected]> wrote:
In some cases the previous algorithm would not return the closest approximation. This would happen when a semi-convergent was the closest, as the previous algorithm would only consider convergents.
As an example, consider an initial value of 5/4, and trying to find the closest approximation with a maximum of 4 for numerator and denominator. The previous algorithm would return 1/1 as the closest approximation, while this version will return the correct answer of 4/3.
To do this, the main loop performs effectively the same operations as it did before. It must now keep track of the last three approximations, n2/d2 .. n0/d0, while before it only needed the last two.
If an exact answer is not found, the algorithm will now calculate the best semi-convergent term, t, which is a single expression with two divisions:
min((max_numerator - n0) / n1, (max_denominator - d0) / d1)This will be used if it is better than previous convergent. The test for this is generally a simple comparison, 2*t > a. But in an edge case, where the convergent's final term is even and the best allowable semi-convergent has a final term of exactly half the convergent's final term, the more complex comparison (d0*dp > d1*d) is used.
Quoted 3 lines
I also wrote some comments explaining the code. While one still needs to look up the math elsewhere, they should help a lot to follow how the code relates to that math.
What are the userspace-visible runtime effects of this change?
Quoted 14 lines · Andrew Morton
Quoted 11 lines · On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <[email protected]> wrote:
In some cases the previous algorithm would not return the closest approximation. This would happen when a semi-convergent was the closest, as the previous algorithm would only consider convergents.
As an example, consider an initial value of 5/4, and trying to find the
closest approximation with a maximum of 4 for numerator and denominator.
The previous algorithm would return 1/1 as the closest approximation,
while this version will return the correct answer of 4/3.
Quoted 1 line
What are the userspace-visible runtime effects of this change?
Ok, I looked into this in some detail.
This routine is used in two places in the video4linux code, but in those cases it is only used to reduce a fraction to lowest terms, which the existing code will do correctly. This could be done more efficiently with a different library routine but it would still be the Euclidean alogrithm at its heart. So no change.
The remain users are places where a fractional PLL divider is programmed. What would happen is something asked for a clock of X MHz but instead gets Y MHz, where Y is close to X but not exactly due to the hardware limitations. After this change they might, in some cases, get Y' MHz, where Y' is a little closer to X then Y was.
Users like this are: Three UARTs, in 8250_mid, 8250_lpss, and
imx. One GPU in vp4_hdmi. And three clock drivers, clk-cdce706, clk-si5351, and clk-fractional-divider. The last is a generic clock driver and so would have more users referenced via device tree entries.
I think there's a bug in that one, it's limiting an N bit field that is offset-by-1 to the range 0 .. (1<<N)-2, when it should be (1<<N)-1 as the upper limit.
I have an IMX system, one of the UARTs using this, so I can provide a real example. If I request a custom baud rate of 1499978, the driver will program the PLL to produce a baud rate of 1500000. After this change, the fractional divider in the UART is programmed to a ratio of 65535/65536, which produces a baud rate of 1499977.0625. Closer to the requested value.