Re: [PATCH] lib: Fix possible incorrect result from rational fractions helper

[Andrew Morton]

On Sat, 30 Mar 2019 13:58:55 -0700 Trent Piepho <tpiepho@xxxxxxxxx> 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.
> 
> 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?