PDQ Algorithm: Infinite precision best fraction within tolerance

[Joe Horn]

Thanks, Pier4r! PDQ was first "officially" presented to HP and friends at HHC 2003. Later, as PDQ developed, that initial version came to be called PDQ1. It was limited to the decimal accuracy of its host machine, because it was implemented on the HP-48 which didn't have infinite-precision integers built-in. It was also slightly slowed down by needing to perform a binary search for intermediate convergents. Here is the paper from the HHC 2003 Proceedings which accompanied that presentation. Needless to say, much of what it says is now obsolete.

http://hhuc.us/2003/files/PDQ1.pdf

PDQ2 was a great improvement, utilizing infinite-precision integers. It was the first version of PDQ which did all its work in the integer domain, thus avoiding all roundoff errors, and allowing PDQ to generate ALL the best fractions for any input, not just the ones up to the host machine's floating-point accuracy. However, it still used a binary search method to find intermediate convergents, because I couldn't figure out a way to avoid that. Here are the associated papers from the HHC 2004 Proceedings. There are many overlaps of information here.

http://hhuc.us/2004/files/PDQ2.pdf
http://hhuc.us/2004/files/PDQ2b.pdf

PDQ3 is the final version of PDQ which avoids the binary search by calculating a single jump to the proper intermediate convergent. That improvement was added by Rodger Rosenbaum. The HP 49/50 code for it was optimized by Tony Hutchins. Other details of PDQ's development history can be found in Pier4r's list above. Here are the final HHC 2012 write-ups about PDQ3, which has come to be known simply as PDQ.

http://hhuc.us/2012/PDQ.TXT <-- describes PDQ3 (AKA PDQ)
http://hhuc.us/2012/PDQ.USR.TXT <-- PDQ in User RPL for study purposes.
http://hhuc.us/2012/PDQ.hp <-- PDQ in binary form for HP49/50