Editing Simple continued fraction (section)

==Best rational approximations==
{{See also|Diophantine approximation|Padé approximant}}

One can choose to define a ''best rational approximation'' to a real number {{mvar|x}} as a rational number {{sfrac|{{mvar|n}}|{{mvar|d}}}}, {{math|''d'' > 0}}, that is closer to {{mvar|x}} than any approximation with a smaller or equal denominator. The simple continued fraction for {{mvar|x}} can be used to generate ''all'' of the best rational approximations for {{mvar|x}} by applying these three rules:

# Truncate the continued fraction, and reduce its last term by a chosen amount (possibly zero).
# The reduced term cannot have less than half its original value.
# If the final term is even, half its value is admissible only if the corresponding semiconvergent is better than the previous convergent. (See below.)

For example, 0.84375 has continued fraction [0;1,5,2,2]. Here are all of its best rational approximations.

:{| class="wikitable"
|- align="center"
! Continued fraction
|  [0;1]  ||  [0;1,3]  ||  [0;1,4]  ||  [0;1,5]  ||  [0;1,5,2]  ||  [0;1,5,2,1]  ||  [0;1,5,2,2] 
|- align="center"
! Rational approximation
| 1 || {{sfrac|3|4}} || {{sfrac|4|5}} || {{sfrac|5|6}} || {{sfrac|11|13}} || {{sfrac|16|19}} || {{sfrac|27|32}}
|- align="center"
! Decimal equivalent
| 1 || 0.75 || 0.8 || ~0.83333 || ~0.84615 || ~0.84211 || 0.84375
|- align="center"
! Error
| +18.519% || −11.111% || −5.1852% || −1.2346% || +0.28490% || −0.19493% || 0%
|}
{{Diophantine_approximation_graph.svg}}

The strictly monotonic increase in the denominators as additional terms are included permits an algorithm to impose a limit, either on size of denominator or closeness of approximation.

The "half rule" mentioned above requires that when {{mvar|a}}{{sub|{{mvar|k}}}} is even, the halved term {{mvar|a}}{{sub|{{mvar|k}}}}/2 is admissible if and only if {{math|{{!}}''x'' − [''a''{{sub|0}} ; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}]{{!}} > {{!}}''x'' − [''a''{{sub|0}} ; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}}/2]{{!}}}}.{{sfn|Thill|2008}} This is equivalent to:{{sfn|Shoemake|1995}}

:{{math|[''a''{{sub|''k''}}; ''a''{{sub|''k'' − 1}}, ..., ''a''{{sub|1}}] > [''a''{{sub|''k''}}; ''a''{{sub|''k'' + 1}}, ...]}}.

The convergents to {{mvar|x}} are "best approximations" in a much stronger sense than the one defined above. Namely, {{mvar|n}}/{{mvar|d}} is a convergent for {{mvar|x}} if and only if {{math|{{!}}''dx'' − ''n''{{!}}}} has the smallest value among the analogous expressions for all rational approximations {{mvar|m}}/{{mvar|c}} with {{math|''c'' ≤ ''d''}}; that is, we have {{math|{{!}}''dx'' − ''n''{{!}} < {{!}}''cx'' − ''m''{{!}}}} so long as {{math|''c'' < ''d''}}. (Note also that {{math|{{!}}''d<sub>k</sub>x'' − ''n<sub>k</sub>''{{!}} → 0}} as {{math|''k'' → ∞}}.)

=== Best rational within an interval ===
A rational that falls within the interval {{open-open|''x'', ''y''}}, for {{math|0 < {{mvar|x}} < {{mvar|y}}}}, can be found with the continued fractions for {{mvar|x}} and {{mvar|y}}. When both {{mvar|x}} and {{mvar|y}} are irrational and
:{{math|''x'' {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}}, ''a''{{sub|''k'' + 1}}, ...]}}
:{{math|''y'' {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ..., ''a''{{sub|''k'' − 1}}, ''b''{{sub|''k''}}, ''b''{{sub|''k'' + 1}}, ...]}}
where {{mvar|x}} and {{mvar|y}} have identical continued fraction expansions up through {{math|''a''<sub>''k''−1</sub>}}, a rational that falls within the interval {{open-open|''x'', ''y''}} is given by the finite continued fraction,
:{{math|''z''(''x'',''y'') {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ''a''{{sub|2}}, ..., ''a''{{sub|''k'' − 1}}, min(''a''{{sub|''k''}}, ''b''{{sub|''k''}}) + 1]}}
This rational will be best in the sense that no other rational in {{open-open|''x'', ''y''}} will have a smaller numerator or a smaller denominator.<ref>{{cite web
 | last = Gosper | first = R. W. | author-link = Bill Gosper
 | title = Appendix 2: Continued Fraction Arithmetic
 | url = https://perl.plover.com/yak/cftalk/INFO/gosper.ps
 | year = 1977}} See "simplest intervening rational", pp. 29–31.</ref><ref>{{cite journal
 | last = Murakami | first = Hiroshi
 | date = February 2015
 | doi = 10.1145/2733693.2733711
 | issue = 3/4
 | journal = ACM Communications in Computer Algebra
 | pages = 134–136
 | title = Calculation of rational numbers in an interval whose denominator is the smallest by using FP interval arithmetic
 | volume = 48}}</ref>

If {{mvar|x}} is rational, it will have ''two'' continued fraction representations that are ''finite'', {{math|''x''<sub>1</sub>}} and {{math|''x''<sub>2</sub>}}, and similarly a rational&nbsp;{{mvar|y}} will have two representations, {{math|''y''<sub>1</sub>}} and {{math|''y''<sub>2</sub>}}. The coefficients beyond the last in any of these representations should be interpreted as {{math|+∞}}; and the best rational will be one of {{math|''z''(''x''<sub>1</sub>, ''y''<sub>1</sub>)}}, {{math|''z''(''x''<sub>1</sub>, ''y''<sub>2</sub>)}}, {{math|''z''(''x''<sub>2</sub>, ''y''<sub>1</sub>)}}, or {{math|''z''(''x''<sub>2</sub>, ''y''<sub>2</sub>)}}.

For example, the decimal representation 3.1416 could be rounded from any number in the interval {{closed-open|3.14155, 3.14165}}. The continued fraction representations of 3.14155 and 3.14165 are
:{{math|3.14155 {{=}} [3; 7, 15, 2, 7, 1, 4, 1, 1] {{=}} [3; 7, 15, 2, 7, 1, 4, 2]}}
:{{math|3.14165 {{=}} [3; 7, 16, 1, 3, 4, 2, 3, 1] {{=}} [3; 7, 16, 1, 3, 4, 2, 4]}}
and the best rational between these two is
:{{math|[3; 7, 16] {{=}} {{sfrac|355|113}} {{=}} 3.1415929....}}
Thus, {{sfrac|355|113}} is the best rational number corresponding to the rounded decimal number 3.1416, in the sense that no other rational number that would be rounded to 3.1416 will have a smaller numerator or a smaller denominator.

=== Interval for a convergent ===
A rational number, which can be expressed as finite continued fraction in two ways,
:{{math|''z'' {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}}, 1] {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}} + 1] {{=}} {{sfrac| ''p''{{sub|''k''}}|''q''{{sub|''k''}}}}}}
will be one of the convergents for the continued fraction expansion of a number, if and only if the number is strictly between (see [https://math.stackexchange.com/a/4438961 this proof])
:{{math|''x'' {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}}, 2] {{=}} {{sfrac| 2''p''{{sub|''k''}} - ''p''{{sub|''k-1''}}|2''q''{{sub|''k''}} - ''q''{{sub|''k-1''}}}}}} and
:{{math|''y'' {{=}} [''a''{{sub|0}}; ''a''{{sub|1}}, ..., ''a''{{sub|''k'' − 1}}, ''a''{{sub|''k''}} + 2] {{=}} {{sfrac| ''p''{{sub|''k''}} + ''p''{{sub|''k-1''}}|''q''{{sub|''k''}} + ''q''{{sub|''k-1''}}}}}}
The numbers {{mvar|x}} and {{mvar|y}} are formed by incrementing the last coefficient in the two representations for {{mvar|z}}. It is the case that {{math|''x'' < ''y''}} when {{mvar|k}} is even, and {{math|''x'' > ''y''}} when {{mvar|k}} is odd.

For example, the number {{sfrac|355|113}} ([[Milü|Zu's fraction]]) has the continued fraction representations
:{{sfrac|355|113}} = [3; 7, 15, 1] = [3; 7, 16]
and thus {{sfrac|355|113}} is a convergent of any number strictly between
:{| cellpadding="2" cellspacing="0"
| align="right" | {{math|[3; 7, 15, 2]}} ||{{=}}|| {{math|{{sfrac|688|219}} ≈ 3.1415525}}
|-
| align="right" | {{math|[3; 7, 17]}} ||{{=}}|| {{math|{{sfrac|377|120}} ≈ 3.1416667}}
|}

=== Legendre's theorem on continued fractions ===
{{see also|Dirichlet's approximation theorem}}
In his ''Essai sur la théorie des nombres'' (1798), [[Adrien-Marie Legendre]] derives a necessary and sufficient condition for a rational number to be a convergent of the continued fraction of a given real number.<ref>{{cite book|last=Legendre|first=Adrien-Marie|author-link=Adrien-Marie Legendre|title=Essai sur la théorie des nombres|date=1798|publisher=Duprat|location=Paris|publication-date=1798|pages=27–29|language=fr}}</ref> A consequence of this criterion, often called '''Legendre's theorem''' within the study of continued fractions, is as follows:<ref>{{cite journal|last1=Barbolosi|first1=Dominique|last2=Jager|first2=Hendrik|date=1994|title=On a theorem of Legendre in the theory of continued fractions|url=https://www.jstor.org/stable/26273940|journal=[[Journal de Théorie des Nombres de Bordeaux]]|volume=6|issue=1|pages=81–94|doi=10.5802/jtnb.106 |jstor=26273940 }}</ref>

'''Theorem'''. If ''α'' is a real number and ''p'', ''q'' are positive integers such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, then ''p''/''q'' is a convergent of the continued fraction of ''α''.
{{collapse top|title = Proof}}
'''Proof'''. We follow the proof given in ''[[An Introduction to the Theory of Numbers]]'' by [[G. H. Hardy]] and [[E. M. Wright]].<ref>{{cite book|last1=Hardy|first1=G. H.|author-link=G. H. Hardy|last2=Wright|first2=E. M.|author-link2=E. M. Wright|title=An Introduction to the Theory of Numbers|title-link=An Introduction to the Theory of Numbers|publisher=[[Oxford University Press]]|year=1938|isbn=|location=London|publication-date=1938|pages=140–141, 153|language=en}}</ref>

Suppose ''α'', ''p'', ''q'' are such that <math>\left|\alpha - \frac{p}{q}\right| < \frac{1}{2q^2}</math>, and assume that ''α'' > ''p''/''q''. Then we may write <math>\alpha - \frac{p}{q} = \frac{\theta}{q^2}</math>, where 0 < ''θ'' < 1/2. We write ''p''/''q'' as a finite continued fraction [''a''<sub>0</sub>; ''a''<sub>1</sub>, ..., ''a<sub>n</sub>''], where due to the fact that each rational number has two distinct representations as finite continued fractions differing in length by one (namely, one where ''a<sub>n</sub>'' = 1 and one where ''a<sub>n</sub>'' ≠ 1), we may choose ''n'' to be even. (In the case where ''α'' < ''p''/''q'', we would choose ''n'' to be odd.)

Let ''p''<sub>0</sub>/''q''<sub>0</sub>, ..., ''p<sub>n</sub>''/''q<sub>n</sub>'' = ''p''/''q'' be the convergents of this continued fraction expansion. Set <math>\omega := \frac{1}{\theta} - \frac{q_{n-1}}{q_n}</math>, so that <math>\theta = \frac{q_n}{q_{n-1} + \omega q_n}</math> and thus,<math display="block">\alpha = \frac{p}{q} + \frac{\theta}{q^2} = \frac{p_n}{q_n} + \frac{1}{q_n (q_{n-1} + \omega q_n)} = \frac{(p_n q_{n-1} + 1) + \omega p_n q_n}{q_n (q_{n-1} + \omega q_n)} = \frac{p_{n-1} q_n + \omega p_n q_n}{q_n (q_{n-1} + \omega q_n)} = \frac{p_{n-1} + \omega p_n}{q_{n-1} + \omega q_n}, </math>where we have used the fact that ''p<sub>n</sub>''<sub>−1</sub> ''q<sub>n</sub>'' - ''p<sub>n</sub>'' ''q<sub>n</sub>''<sub>−1</sub> = (-1)''<sup>n</sup>'' and that ''n'' is even.

Now, this equation implies that ''α'' = [''a''<sub>0</sub>; ''a''<sub>1</sub>, ..., ''a<sub>n</sub>'', ''ω'']. Since the fact that 0 < ''θ'' < 1/2 implies that ''ω'' > 1, we conclude that the continued fraction expansion of ''α'' must be [''a''<sub>0</sub>; ''a''<sub>1</sub>, ..., ''a<sub>n</sub>'', ''b''<sub>0</sub>, ''b''<sub>1</sub>, ...], where [''b''<sub>0</sub>; ''b''<sub>1</sub>, ...] is the continued fraction expansion of ''ω'', and therefore that ''p<sub>n</sub>''/''q<sub>n</sub>'' = ''p''/''q'' is a convergent of the continued fraction of ''α''.
{{collapse bottom}}

This theorem forms the basis for [[Wiener's attack]], a polynomial-time exploit of the [[RSA (cryptosystem)|RSA cryptographic protocol]] that can occur for an injudicious choice of public and private keys (specifically, this attack succeeds if the prime factors of the public key ''n'' = ''pq'' satisfy ''p'' < ''q'' < 2''p'' and the private key ''d'' is less than (1/3)''n''<sup>1/4</sup>).<ref>{{cite journal|last=Wiener|first=Michael J.|date=1990|title=Cryptanalysis of short RSA secret exponents|url=https://ieeexplore.ieee.org/document/54902|journal=[[IEEE Transactions on Information Theory]]|volume=36|issue=3|pages=553–558|doi=10.1109/18.54902 |via=IEEE}}</ref>