Over the weekend, I was playing with my toy version of complex-rationalize.
The problem in programming this function isn't the complex numbers themselves,
but what the "stopping criterion" for the continued fraction should be.
In particular, I notice that the Lisp (& probably the Maxima) version of
"rationalize" doesn't do a very good job of stopping. For example,
the CF expansion of sqrt(2)=[1,2,2,2,2,2,...], so if the CF expansion
starts spitting out non-2's, then Houston, we have a Problem. The
Common Lisp implementations I have (GCL, SBCL) both seem to go too far.
According to the Common Lisp manual, "rationalize" may return any rational
number for which the floating-point number is the best available approximation
of its format; in doing this it attempts to keep both numerator an denominator
small.
The Common Lisp manual further goes on to stipulate that
(float (rationalize x) x) == x
So, one might conclude that the problem isn't rationalize itself, but the
implementation of sqrt(2).
Nevertheless, I think that "rationalize" should have a second argument
to indicate the precision of the result -- e.g., |x-x'|/|x|<epsilon,
where x is the number being rationalized, and x' is the rational
approximation.
But even implementing this stopping criterion is fraught with problems.
It is possible to implement a recursive Euclidean algorithm which
is _tail-recursive_, i.e., it builds the product of 2x2 matrices
while recursing down, rather than while returning back up (this
works due to the associativity of matrix multiplication). When
the stopping criterion is reached, the matrix (and hence the
rational approximation) has already been built and merely needs
to be returned.
But even when this is done, the programming task is hampered by
the fact that Common Lisp rationals won't allow "1/0" (one/zero).
This is a pity, because the 1) IEEE floating point numbers already
allow such an unsigned infinity; and 2) the most perspicuous code
allows rationals of the form "1/0" to exist, because error'ing
out forces too many, and too early, tests to avoid them.