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. > > 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?
