PDQ Algorithm: Infinite precision best fraction within tolerance
03-28-2014, 10:47 AM
Post: #5
 Joe Horn Senior Member Posts: 2,004 Joined: Dec 2013
RE: PDQ Algorithm: Infinite precision best fraction within tolerance
(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.

<0|ΙΈ|0>
-Joe-
 « Next Oldest | Next Newest »

 Messages In This Thread PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 12-13-2013, 05:09 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Thomas_Sch - 02-16-2014, 02:01 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Han - 02-16-2014, 02:32 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - patrice - 03-26-2014, 10:10 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 03-28-2014 10:47 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 05-28-2014, 05:37 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - dbbotkin - 10-08-2014, 12:56 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 12-06-2014, 05:35 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - patrice - 12-06-2014, 10:47 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 12-06-2014, 02:38 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - patrice - 12-06-2014, 05:06 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 12-07-2014, 04:30 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - patrice - 12-07-2014, 08:51 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 12-08-2014, 12:10 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - pier4r - 03-15-2018, 03:20 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Luigi Vampa - 03-15-2018, 08:50 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 03-16-2018, 02:41 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - pier4r - 03-28-2018, 06:57 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - smartin - 02-24-2019, 08:36 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - cdmackay - 02-24-2019, 10:29 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 02-25-2019, 11:10 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - cdmackay - 02-25-2019, 05:56 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 02-26-2019, 03:17 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - cdmackay - 02-26-2019, 03:45 PM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - cdmackay - 01-26-2020, 12:32 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - Joe Horn - 01-26-2020, 02:41 AM RE: PDQ Algorithm: Infinite precision best fraction within tolerance - cdmackay - 01-26-2020, 08:34 PM

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