Threaded Mode | Linear Mode

Joe Horn · 03-28-2014, 10:47 AM

(03-26-2014 10:10 AM)patrice Wrote:
(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.

Yes, that was my point: the PDQ algorithm and Farey fractions find it, but the standard "continued fraction algorithm" (as used by everybody but HP) misses all intermediate convergents.

(03-26-2014 10:10 AM)patrice Wrote: The counterpart is that Farey is slow to converge for values near an integer.

This is one of PDQ's unique strengths; it doesn't spend any time searching through intermediate convergents. As soon as it determines that the best fraction MIGHT lie between two principal convergents, it performs a single calculated jump to the best one. This is important when there are thousands of intermediate convergents in a row (which happens whenever there are very large partial quotients in the continued fraction expansion).

(03-26-2014 10:10 AM)patrice Wrote:
(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.

It would be very helpful (and fun!) to have a CAS version of your Farey fraction programs, so that they could use "infinite precision" integers to overcome Home's 12-digit limitation. Then we could really compare the performance of PDQ vs. Farey fractions on challenging inputs.