PDQ, an HP49/50 program that finds the simplest fraction that approximates a target value within a given tolerance.
by Joe Horn, Rodger Rosenbaum, and Tony Hutchins.
Related files included on the HHC 2012 Thumb Drive:
PDQ.hp -- Binary version of the PDQ program for the HP49/50 series only. Hybrid of User RPL and System RPL, embedded in a Code object. Transfer it to your calculator with Conn4x or similar.
PDQ.USR.TXT -- Non-optimized User RPL version in source code form. Useful only for studying the algorithm.
PDQ.TXT -- This document.
---------------------------------------------------------------------
PDQ program instructions:
Input:
2: Target value (J)
1: Tolerance (T)
Output:
2: 'p/q'
1: X or N: error
These might be easiest to understand by looking at the examples a few paragraphs below.
The target value can be expressed in three ways:
a) A floating-point decimal fraction (aka "real number"), e.g. 3.14159365359 or .0015378446
b) A ratio of two integers as an algebraic object, e.g. '37/48'.
c) A string containing a floating-point number, e.g. "3.1415926535897932384626"
Real numbers are limited to 12 digits; ratios and strings may contain an unlimited number of digits.
The Tolerance can be expressed in three ways:
a) A real number.
b) A positive integer.
c) A ratio of two integers as an algebraic object.
If the tolerance is a real number, then it is used as-is.
If the tolerance is a positive integer T, then the tolerance is set to 1/10^T. This feature is intended to save you a few milliseconds. For example, to set a tolerance of "6 decimal places", you can simply input 6 instead of having to type 0.000001 or 1E-6. If the tolerance exceeds the number of digits of the input target, then trailing zeros are assumed to be significant digits. For example, if the target is 3.14159265359 and the tolerance is set to 15, then the target will be assumed to be exactly 3.141592653590000 (including the trailing zeros).
If the tolerance is a ratio, it is used as-is. It may contain an unlimited number of digits.
The 'p/q' output on level 2 is the simplest fraction that lies in the interval J +/- T. There is always a unique answer, and PDQ always finds it.
The output on level 1 serves two purposes.
1) It is tagged with an "N" if the result is "Normal", or an "X" if it is one of the "eXtra" solutions that most calculators can't find.
2) The fraction in level 1 is the exact difference between the input and the output. Therefore pressing [-] [EVAL] returns the original input.
Examples:
(1) What is the best fraction for pi, accurate to 7 decimal places?
[pi] [->NUM] 7 [PDQ] --> 75948/24175 X:-9602153/96700000000000
This means all of the following:
(a) 75948/24175 lies within 10^(-7) of 3.14159265359.
(b) There exists no fraction with a smaller numerator or denominator which is that close to pi.
(c) Most calculators cannot find this solution, because its continued fraction expansion is not a proper subset of the continued fraction for 3.14159265359.
(d) 75948/24175 differs from 3.14159265359 by exactly -9602153/96700000000000.
(2) What is the simplest fraction between pi and the square root of 10?
Convert the problem into a target (average of pi and the square root of 10) and a tolerance (half of their difference):
10. [sqrt] [pi] [->NUM]
[-] [LASTARG] [+] 2 [/] [SWAP] 2 [/] [PDQ]
--> 22/7
(3) What is the best approximation for pi accurate to 14 decimal places?
That's more decimal places than RPL allows in real numbers, so let's input 15 decimal places in string form.
"3.141592653589793" 14 [PDQ]
--> 58466453/18610450
The "X" on level 1 indicates that this is an "eXtra" solution that most calculators cannot find.
Press [ENTER] [->NUM] and see that it's only off by about 9E-15.
Then press [DROP] [-] [EVAL] and see your original input.
Instead of "3.141592653589793", we could also have input
3141592653589793/1000000000000000.
(4) If an opinion poll reports that 12.345% of the respondents voted "Yes", then what is the smallest number of people who could have been polled? Assume that the statistic was rounded to three decimal places.
When rounded to 3 places, anything between 12.3445% (inclusive) and 12.3455 (exclusive) becomes 12.345%.
Terefore our target is 0.12345 ("%" means :divided by 100") and the tolerance is 0.000005.
.12345 .000005 [PDQ] --> 139/1126
If 139 people out of 1126 answered "Yes", then 12.345% (rounded to 3 places) answered "Yes", and that's guaranteed (by PDQ!) to be the smallest possible sample to yield that statistic. Notice the "X" on level 1; if this question were on an exam, your friends' calculators would probably give them the wrong answer!
(5) Is there a way to automate PDQ to just give the "best" fraction for a 12-digit calculator without making me think about the tolerance?
Yes. Use this little program to call PDQ. It calculates the necessary tolerance automatically:
<< ->NUM DUP XPON 12. - ALOG 5. * PDQ DROP >>
Input: Any number or algebraic expression.
Output: The simplest fraction that evaluates to the same thing as the input.
Example: Input the square root of 2; it yields 665857/470832, which evaluates to the same thing as the square root of 2 on a 12-digit calculator, and it's better than the solution given by the ->Q function.
Further information about PDQ can be gleaned from the "comp.sys.hp48" Usenet newsgroup (available on "Google Groups") by searching for "PDQ". The PDQ Algorithm was first presented to the world at HHC 2003 by Joe Horn, and it has been his obsession ever since. You'll tickle his toes if you correspond with him about it: joehorn@holyjoe.net