(Comp.sys.handhelds)
Item: 2604 by billw at hpcvra.cv.hp.com.
Author: [William C Wickes]
  Subj: ->Q or Not ->Q
  Date: Tue Apr 02 1991

From the HP 48 Design Team:


               ->Q OR NOT ->Q, THAT IS THE QUESTION

Thanks to Joseph Horn, the HP28/48 community now has additional fast
rationalization functionality for their machines  [Note: see DEC2FRAC on this
disk.  -jkh-]  We congratulate him for this elegant solution!  There are a
number of interesting points regarding DEC2FRACs relation to ->Q which deserve
some mention.  Perhaps these will stimulate discussion and further
contributions.

DEC2FRAC is an addition and not a replacement for ->Q because its aim is rather
different.  DEC2FRAC's aim is to produce the fraction with the _smallest error_
and a given denominator size.  ->Q's aim is to produce the fraction with the
_smallest denominator_ and a given error size.  This is best illustrated with
the golden mean, '(1+\sqr(5))/2'.  Given this and 1E11, DEC2FRAC returns
'139583862445/86267571272' while ->Q returns (in STD mode) '514229/317811'.
When evaluated, these return _exactly_ the same floating point number.  The
idea of ->Q is to "round to simpler" rather than "round to closer." This is
useful where you have what you believe to be a "simple" fraction contaminated
with roundoff or other noise.

The HP48 manuals did little to clarify this issue, especially since we wanted
to make no specific claim with only a conjecture of correctness.  In this
regard, posting a proof that the algorithm fills in all possible fractions
would be a great boon to the community.

While for many "interesting" numbers the continued fraction sequence as
generated by DUP IP SWAP FP INV ...  is exact, even though the floating point
representation is not, in other cases, you get "noise" unexpectedly early.
Does this have any significance regarding the "safety" of generating the
numerator of the fraction from the denominator by division?

While ->Q keeps around the entire continued fraction sequence entailing some
speed penalty, there may be other statistics about the sequence (such as
periodicity) which can be of interest in "deciphering" a floating point number.
Suggestions along these lines are most welcome.

Thanks again to J. Horn for a stimulating and useful post.