(12C) Decimal to Fraction

[Albert Chan]

(08-07-2018 12:49 PM)Albert Chan Wrote:  Your Pi example illustrate even better, fraction with denominator <= 100:
continued fraction of pi => 22/7 = 3.142857
pi.limit_denominator => 311/99 = 3.141414 --> about 7X more accurate

Peeking inside Python fractions.py, I learned the procedure: (limit_denominator method)
It is continued fractions ... with a twist

using above example, pi is bounded by 2 continued fractions, both with denomination below 100

3/1 < pi < 22/7

pi = (3 + 22k) / (1 + 7k) for some k (k=0, we get 3/1, k=infinity, we get 22/7)

if k is integer, the best is k=15, next continued fraction, 333/106, slightly under-estimated (*)
Any lowered k will under-estimate more, but perhaps better than 22/7

So, we solve for biggest denominator <= 100, we get k=14

(3+22*14)/(1+7*14) < pi < 22/7
311/99 < pi < 22/7

pick the one closest to pi, thus return 311/99

(*) actually, the best is when k=16, getting the ubiquitous 355/113.

Continued fraction coefficient only uses the integer part, and not the closest integer.
This setup guaranteed the value bounded between 2 continued fractions.
So, without using a calculator to confirm, 333/106 < pi < 355/113