PDQ Algorithm: Infinite precision best fraction within tolerance

[patrice]

(12-13-2013 05:09 AM)Joe Horn Wrote:  Example #1: What is the best fraction that's equal to pi plus or minus 1/800? Answer: 179/57, which is the same answer as given by Patrice's FareyDelta program. This is a difficult problem, because 179/57 is not a principal convergent of pi.

Not a big deal for a program that use Farey series because the Farey series try all the intermediate fractions until it find one within tolerance.
The counterpart is that Farey is slow to converge for values near an integer.

(12-13-2013 05:09 AM)Joe Horn Wrote:  Example #2: What is the best fraction that's equal to pi plus or minus 10^-14? FareyDelta can't handle that problem, because it is limited by the 12-digit accuracy of Home math. PDQ gets the right answer, though: 58466453/18610450.

That's Home math limitation.