2

I've read in Wikipedia:

By stopping once the desired precision is reached, floating-point numbers can be approximated to arbitrary precision. If a real number x is approximated by any rational number a/b that is not in the sequence of mediants found by the algorithm above, then the sequence of mediants contains a closer approximation to x that has a denominator at most equal to b; in that sense, these mediants form the best rational approximations to x.

Suppose you have a rational $0 < q = \frac{a}{b} < 1$ and you want to find $\tilde q = \frac{\tilde a}{\tilde b}$ such that $\Delta = |q- \tilde q| < \frac{1}{n}$. How long deep would you have to descent in the tree?

By looking at the tree, I got:

  • without any decent ($d=0$), you can guarantee $\Delta < 1$
  • $d=1 \Rightarrow \Delta < \frac{1}{2}$
  • $d = 2 \Rightarrow \Delta < \frac{1}{3}$
  • $d = 3 \Rightarrow \Delta < \frac{1}{4}$

So it looks very much like:

$d \Rightarrow \Delta < \frac{1}{d+1}$. I guess this is plausible, as the worst case seems to be something close to $0$.

But is there a way to get a better approximation? I mean, suppose you have to approximate $q_1 = 0.7320508$. Then you would get these results:

  1. $\frac{1}{1}$, $\Delta = 0.26794920$
  2. $\frac{1}{1}$, $\Delta = 0.26794920$
  3. $\frac{1}{2}$, $\Delta = 0.23205080$
  4. $\frac{2}{3}$, $\Delta = 0.06538413$
  5. $\frac{3}{4}$, $\Delta = 0.01794920$
  6. $\frac{5}{7}$, $\Delta = 0.01776509$
  7. $\frac{8}{11}$, $\Delta = 0.00477807$
  8. $\frac{11}{15}$, $\Delta = 0.00128253$
  9. $\frac{19}{26}$, $\Delta = 0.00128157$
  10. $\frac{30}{41}$, $\Delta = 0.00034348$
  11. $\frac{41}{56}$, $\Delta = 0.00009206$
  12. $\frac{71}{97}$, $\Delta = 0.00009204$
  13. $\frac{112}{153}$, $\Delta = 0.00002466$
  14. $\frac{153}{209}$, $\Delta = 0.00000662$
  15. $\frac{265}{362}$, $\Delta = 0.00000660$
  16. $\frac{418}{571}$, $\Delta = 0.00000176$
  17. $\frac{571}{780}$, $\Delta = 0.00000048$
  18. $\frac{989}{1351}$, $\Delta = 0.00000047$
  19. $\frac{1560}{2131}$, $\Delta = 0.00000012$

But when I have $q_2 = \frac{1}{2} + \frac{1}{100000}$ I know it will take VERY long until I get an improvement. Intuitively, I'd say it would take something about $\frac{100000}{2} + 1$ steps until the approximation gets better.

Question

Given a real number $q = \frac{a}{b}$ and an approximation $\tilde q = \frac{\tilde a}{\tilde b}$ in step $d$, is there any better guarantee for approximations in step $d+i$ with $i > 0$?

Or is there any way to tell after how many steps an improvement will happen at all?

Martin Thoma
  • 9,821

1 Answers1

1

Your approximation for Stern Brocot steps is not far off, but in practice I found it to be about 100,000/4 rather than 100,000/2.

Using continued fractions, which is a simple extension to Stern Brocot, I got very close to your fraction in 4 steps, and got it exactly in 6 steps.

cumulative continued fraction steps: 1 new Stern Brocot steps: 0 fraction: 0/1 error: 0.50001

cumulative continued fraction steps: 2 new Stern Brocot steps: 1 fraction: 1/1 error: -0.49999

cumulative continued fraction steps: 3 new Stern Brocot steps: 1 fraction: 1/2 error: 9.99999999995e-06

cumulative continued fraction steps: 4 new Stern Brocot steps: 24999 fraction: 25000/49999 error: -2.00004013351e-10

cumulative continued fraction steps: 5 new Stern Brocot steps: 1 fraction: 25001/50001 error: 1.99995908723e-10

cumulative continued fraction steps: 6 new Stern Brocot steps: 1 fraction: 50001/100000 error: 0.0

The worst possible value to find is an approximation to phi, the golden ratio. In this case continued fractions give no advantage of Stern Brocot. Continued fractions approximated phi by the ratio of consecutive terms of the Fibonacci series.

After 13 steps, continued fractions converge to phi with an error < 1e-5. So in the worst case your example would be found very closely in 13 steps, though it is actually found closely in 4 steps. Searching for a fraction, the worst case formula to get close would be something like (log(base phi)1/error)/2 + 1 steps.

The denominators get larger than your fractions in 26 steps, so I would imagine that it would have to be found before then, worst case. So the worst case would be something close to log(base phi)denominator.

(edit for proof)

http://en.wikipedia.org/wiki/Euclidean_algorithm#Worst-case_number_of_steps

Relationship between s-b tree and continued fractions:

http://www.cut-the-knot.org/blue/ContinuedFractions.shtml

Finding continued fractions is identical to the euclidean algorithm. The worst case number of steps for Euclidean algorithm are between consecutive Fibonacci numbers. Therefore the worst case number of steps for finding a ratio is the ratio of consecutive Fibonacci numbers.

The ratio of consecutive Fibonacci numbers converges to phi. The worst number of steps for any real number is at phi.

Sorry still not rigorous, but I'm sure you can fill in the gaps

Richard
  • 376
  • I miss a proof or a source for your claims. – Martin Thoma Apr 29 '14 at 12:35
  • Sorry, I played with continued fractions 2 years ago. I did a quick google, but I have no idea where the source material is. Just thought you may be interested. :-) If you find the source material feel free to update the answer. – Richard Apr 29 '14 at 12:41
  • I remember it was related to phi being the "most irrational number" – Richard Apr 29 '14 at 12:50
  • If you have never come across continued fractions, first look at the Euclidean algorithm, and work from there. Then have a look at the above proof. Naive Stern Brocot implementation is like subtracting the small number from the larger one at a time, rather than simply finding the remainder in one step which is what continued fractions does. – Richard Apr 29 '14 at 13:10
  • @moose - I have answered your question with a proof and a worked example. What more do you want? After 6 months do you really think you are going to get a better answer? – Richard May 01 '14 at 22:54
  • If I understand your answer correct, you simply tell me how long I have to descent in the stern brocot tree for one specific example. That' simple to answer and that was not my question. My question was: How long should you descent in Stern-Brocot-Tree to get a fixed approximation guarantee [without actually calculating the approximation and without knowing which number you will approximate]? You say "The worst possible value to find is an approximation to phi, the golden ratio." - why is that the worst case? What is the relationship betwwen continued fractions and the s-b-tree? – Martin Thoma May 03 '14 at 13:29
  • @moose - Step 1: S-B trees are just slow versions of continued fractions. I have added another link in the answer to that effect. Step 2: the algorithm for continued fractions is exactly the Euclidean algorithm. The algorithm for S-B is equivalent to finding a modulus by repeated subtraction rather than doing a division and finding the remainder. Either way, your question translates into a question about the Euclidean algorithm – Richard May 03 '14 at 23:39
  • Step 3: I have put in a link that explains why the Fibonacci series are exactly the worst performing numbers for the Euclidean algorithm. It follows directly that ratios of Fibonacci numbers are the numbers for which continued fractions most slowly approach the target ratio. Step 4: Ratios of Fibonacci numbers progressively approximate phi. Step 5: Therefore, the ratio by which continued fractions progressively approximate an irrational number is at phi. – Richard May 03 '14 at 23:44
  • There is, in fact, more discussion of the 'subtraction-only' version of the Euclidean algorithm in volume 2 of Don Knuth's The Art Of Computer Programming; IIRC the number of steps expands from $O(\log q)$ to $O(\log^2 q)$, but my copy seems to be on permanent loan-out and so I can't check for certain. – Steven Stadnicki May 03 '14 at 23:45
  • (Edit) Step 5: Therefore, the algorithm used to calculate progressive continued fraction approximations of an irrational number performs worst (is slowest at becoming more accurate) at phi. – Richard May 03 '14 at 23:56
  • @StevenStadnicki Thanks for that. I think that is the average number of steps - am I correct? Moose engineered an example close to the worst number of steps which was O(q), specifically for n/d, the number of steps was d/4. – Richard May 04 '14 at 00:05
  • @Richard Right - Equivalently, you can always be forced to do $\Theta(n)$ subtractions in your first simulated 'division' step. – Steven Stadnicki May 04 '14 at 00:33