Using the closest integer ("round" = least absolute remainder) isn't new. I don't have my Knuth V.I handy, but I think that using "round" instead of "floor" is several hundred years old. Rounding is also necessary for convergence in the complex plane -- e.g., for Gaussian integer gcd's. See this discussion: http://home.pipeline.com/~hbaker1/Gaussian.html My new (?) idea is focusing on the circle itself, rather than the point, BTW, the inverse of a circle (C,r) is the circle (C',r)/(CC'-r^2), and as you can imagine, things get very hairy when r^2=CC' -- i.e., when the circle goes directly through the origin. If the circle to be inverted encloses the origin, then its inverse will be "inside out" -- i.e., it will enclose infinity (oo), but exclude the origin. For small r, one could approximate 1/(CC'-r^2) with a Taylor expansion: 1/(CC'-r^2) ~ 1/(CC')(1+r^2/(CC')+...) So if we choose a smaller radius to take account of the approximation for the center point, then we might be able to use this Taylor expansion until r^2>1/2, which is all we will ever need. ---- Note that the sequence of partial quotients is slightly different from the classical algorithm. In particular, my algorithm might be "too" good, in the sense that it might not return the _worst_ approximation that fits within the original circle, but one that is "one click" better. If you are really looking for the worst approximation -- i.e., the one with the smallest denominator, my algorithm may not produce it. ---- It should be possible to get an estimate on the roundoff error involved in these procedures by carrying out 2 parallel computations: the traditional one using floating point numbers, and mine using rational numbers; we just have to agree on the partial quotients. Since the Mobius transform is rational and hence exact, if we ever arrive at a situation where the point to be approximated no longer lies "inside" its own circle, then we have clear evidence of roundoff error, and we must stop -- this is the best approximation we're going to be able to get within the limits of machine precision. At 01:04 PM 7/8/2012, Adam P. Goucher wrote:
That is absolutely brilliant! It seems to resemble the process of generating a continued fraction approximation of a complex number:
1. Subtract [z] from z, where [] indicates the closest Gaussian (or Eisenstein, or whatever) integer.
2. Raise z to the power of -1 (i.e. invert in the unit circle and conjugate).
3. Repeat the first two steps ad infinitum.
This differs from the ordinary CF algorithm in that the closest integer, rather than the floor, is chosen at each stage (as floor is meaningless in an unordered set such as the complex numbers). Let's see how this version produces a different CF for pi:
Ordinary: [3;7,15,1,292,1,1,1,2,1,...] Modified: [3;7,16,-294,3,-4,5,-15,-3,2,...]
I decided to search the OEIS for this sequence:
--------
What about exp(1)? According to Mathematica, it is:
[3; -4, 2, 5, -2, 7, -2, 9, -2, -11, ...]
This is only slightly more complicated than the regular continued fraction for e. And exp(i) using Gaussian integers?
[1+i; -2+i, 1+3i, -2, 1-5i, -2, 1+7i, -2, 1-9i, -2, 1+11i, ...]
Very similar. What about exp(2)?
[7; 3, -2, -3, -18, -6, 2, 6, 30, 9, -2, -9, -42, -12, 2, 12, 54, 15, -2, -15, -66, -18, 2, 18, 78, 21, -2, -21, -90, -24, ...]
Excluding the obvious sign alteration, the columns are all basic arithmetic progressions. exp(3)?
[20; 12, -3, -4, -4, 7, -3, -17, 2, 16, 2, 13, 14, 4, 6, 3, -2, -2, -2, -2, -3, -6, 5, -2, -68, -7, -6, 5, 3, -3, ...]
Hmm, that appears completely irregular! Maybe it is still a simple interleaving of arithmetic progressions, but with a very large period. Let's try exp(1/2):
[2; -3, 7, -2, -10, 2, 14, -2, -18, 2, 22, -2, -26, 2, 30, ...]
Again, very regular. --------
Note that these continued fractions (of irrational numbers) do not permit the appearance of ones, in the same way that an ordinary CF cannot contain zeroes. Phi has the simplest CF; I wonder what has the 'simplest' modified CF of [2; 2, 2, 2, 2, 2, 2, ...].
Well, there's the obvious recurrence x = 2 + 1/x, which leads to the quadratic equation x^2 - 2x - 1 = 0 with positive real root 2 + sqrt(2). --------
Sincerely,
Adam P. Goucher