3 ms·
Your assumption is pretty good! I won't use continued fractions directly but the Stern-Brocot tree method can be understood in terms of continued fractions.
by ericlippert 11y ago
Your assumption is pretty good! I won't use continued fractions directly but the Stern-Brocot tree method can be understood in terms of continued fractions.
- jason_s 11y agooh right -- mediants! I've never heard of Stern-Brocot but I know what it is. Why not just use continued fractions directly? https://en.wikipedia.org/wiki/Continued_fraction#Calculating_continued_fraction_representations https://en.wikipedia.org/wiki/Continued_fraction#Calculating... e.g. p = 3.141592653589793 = 3 + 1 / 7.062513305931052 = 3 + 1 / (7 + 1 / 15.996594406684103) = 3 + 1 / (7 + 1 / (15 + 1 / 1.0034172310150002)) = 3 + 1 / (7 + 1 / (15 + 1 / (1 + 1/292.63459087501246))) so the continued fraction coefficients are 3;7;15;1;292 (see http://mathworld.wolfram.com/PiContinuedFraction.html http://mathworld.wolfram.com/PiContinuedFraction.html or https://en.wikipedia.org/wiki/Continued_fraction#Continued_fraction_expansions_of_.CF.80 https://en.wikipedia.org/wiki/Continued_fraction#Continued_f...) and can be converted to rationals at each step using the semiconvergent recursion formula https://en.wikipedia.org/wiki/Continued_fraction#Semiconvergents https://en.wikipedia.org/wiki/Continued_fraction#Semiconverg... to get approximants 3/1, 22/7, (3 + 15 * 22) / (1 + 15 * 7) = 333/106, (22 + 1 * 333) / (7 + 1 * 106) = 355/113, (333 + 292 * 355) / (106 + 292 * 113) = 103993/33102, etc.