PDQ Algorithm: Infinite precision best fraction within tolerance

03282014, 10:47 AM
Post: #5




RE: PDQ Algorithm: Infinite precision best fraction within tolerance
(03262014 10:10 AM)patrice Wrote:(12132013 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. 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. (03262014 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). (03262014 10:10 AM)patrice Wrote:(12132013 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 12digit accuracy of Home math. PDQ gets the right answer, though: 58466453/18610450. 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 12digit limitation. Then we could really compare the performance of PDQ vs. Farey fractions on challenging inputs. <0ΙΈ0> Joe 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)