13
\$\begingroup\$

Related: Cleaning up decimal numbers

Background

A continued fraction is a way to represent a real number as a sequence of integers in the following sense:

$$ x = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{\ddots + \cfrac{1}{a_n}}}} = [a_0; a_1,a_2,\cdots,a_n] $$

Finite continued fractions represent rational numbers; infinite continued fractions represent irrational numbers. This challenge will focus on finite ones for the sake of simplicity.

Let's take \$\frac{277}{642}\$ as an example. It has the following continued fraction:

$$ \frac{277}{642} = 0 + \cfrac{1}{2 + \cfrac{1}{3 + \cfrac{1}{6 + \cfrac{1}{1 + \cfrac{1}{3 + \cfrac{1}{3}}}}}} = [0;2, 3, 6, 1, 3, 3] $$

If we truncate the continued fraction at various places, we get various approximations of the number \$\frac{277}{642}\$:

$$ \begin{array}{c|c|c|c} \style{font-family:inherit}{\text{Continued Fraction}} & \style{font-family:inherit}{\text{Fraction}} & \style{font-family:inherit}{\text{Decimal}} & \style{font-family:inherit}{\text{Relative error}}\\\hline [0] & 0/1 & 0.0\dots & 1 \\\hline [0;2] & 1/2 & 0.50\dots & 0.15 \\\hline [0;2,3] & 3/7 & 0.428\dots & 0.0067 \\\hline [0;2,3,6] & 19/44 & 0.4318\dots & 0.00082 \\\hline [0;2,3,6,1] & 22/51 & 0.43137\dots & 0.00021 \\\hline [0;2,3,6,1,3] & 85/197 & 0.431472\dots & 0.000018 \\\hline [0;2,3,6,1,3,3] & 277/642 & 0.4314641\dots & 0 \end{array} $$

These are called convergents of the given number. In fact, the convergents are the best approximations among all fractions with the same or lower denominator. This property was used in a proposed machine number system of rational numbers to find the approximation that fits in a machine word of certain number of bits.

(There are some subtle points around "best approximation", but we will ignore it and just use the convergents. As a consequence, if your language/library has a "best rational approximation" built-in, it is unlikely to correctly solve the following task.)

Task

Given a rational number \$r\$ given as a finite continued fraction and a positive integer \$D\$, find the best approximation of \$r\$ among its convergents so that its denominator does not exceed \$D\$.

The continued fraction is guaranteed to be a finite sequence of integers, where the first number is non-negative, and the rest are strictly positive. You may output the result as a built-in rational number or two separate integers. The output fraction does not need to be reduced.

Standard rules apply. The shortest code in bytes wins.

Test cases

[0, 2, 3, 6, 1, 3, 3], 43 => 3/7
[0, 2, 3, 6, 1, 3, 3], 44 => 19/44
[5, 6, 7], 99 => 222/43
\$\endgroup\$
1
  • \$\begingroup\$ I've edited the Mathjax slightly to use \cfrac, the recommended usage for continued fractions \$\endgroup\$ Apr 6 at 12:42
8
\$\begingroup\$

JavaScript (ES6),  72 68   67 bytes

Expects (max_denominator)(seq). Returns [numerator, denominator].

m=>g=([v,...a],n=0,d=1,N=1,D=0)=>(d+=D*v)<=m?g(a,N,D,N*v+n,d):[N,D]

Try it online!

Commented

m =>             // outer function taking m = maximum denominator
g = (            // inner recursive function taking:
  [v,            //   v = next term from the continued fraction
      ...a],     //   a[] = remaining terms
  n = 0,         //   n = previous numerator
  d = 1,         //   d = previous denominator
  N = 1,         //   N = current numerator
  D = 0          //   D = current denominator
) =>             //
  (d += D * v)   // we compute the new denominator d = D * v + d
                 // this results in NaN if v is undefined,
                 // which forces the comparison to fail
  <= m ?         // if it's less than or equal to m:
    g(           //   do a recursive call:
      a,         //     pass the remaining terms of the continued fraction
      N, D,      //     pass the current numerator and denominator
      N * v + n, //     pass the new numerator
      d          //     pass the new denominator
    )            //   end of recursive call
  :              // else:
    [N, D]       //   we're done: return [N, D]
\$\endgroup\$
4
\$\begingroup\$

J, 25 23 bytes

(]{:@#~0#.>:)2 x:(+%)/\

Try it online!

-2 thanks to Bubbler

how

We'll use 43 f 0, 2, 3, 6, 1, 3, 3x as an example...

  • (+%)/\ For each prefix \, reduce from the right / using the J hook (+%), which adds its left arg to the inverse of its right argument. This returns rational numbers:

    0 1r2 3r7 19r44 22r51 85r197 277r642
    
  • 2 x: Convert to pairs:

    0   1
    1   2
    3   7
    19  44
    22  51
    85  197
    277 642
    
  • ]...#~... Filter that list for valid denominators with the following mask:

    • >: Is each number less than or equal to the left arg:

      1 1
      1 1
      1 1
      1 0
      1 0
      0 0
      0 0
      
    • 0#. Convert to a "base 0" number. This will be 1 only for pairs whose 2nd element (denominator) is 1:

      1 1 1 0 0 0 0
      
  • Our filtered list becomes:

    0   1
    1   2
    3   7
    
  • {:@ Return the last element.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 2|&#. can be 0#.. \$\endgroup\$
    – Bubbler
    Apr 6 at 5:43
  • \$\begingroup\$ @Bubbler Ha! I love it. \$\endgroup\$
    – Jonah
    Apr 6 at 5:44
3
\$\begingroup\$

Stax, 14 bytes

╪£pÇUßi⌂Ω♫M⌂░◘

Run and debug it

takes inputs as <max denominator>,<continued fraction>.

Explanation

|[{r{su+km{Rn^<oH
|[{      m        for each prefix of the continued fraction
   r               reverse
    {   k          reduce by:
     su+            swap, reciprocal and add
          {    o  order by:
           R       denominator
            n^<    lesser than 2nd input + 1 ? 
                H last element
\$\endgroup\$
3
\$\begingroup\$

Wolfram Language (Mathematica), 47 bytes

Last@*Cases[a_/;Denominator@a<=#]@*Convergents&

Try it online!

-25 bytes from @att

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 47 bytes taking [D][r] (FromContinuedFraction isn't necessary) \$\endgroup\$
    – att
    Apr 6 at 5:47
2
\$\begingroup\$

Charcoal, 38 bytes

FLθ«≔⟦§θι¹⟧ζF⮌…θι≔⁺⁺⊟ζ×ζκζζ¿¬›§ζ¹ηP⪫ζ/

Try it online! Link is to verbose version of code. Explanation:

FLθ«

Loop over the prefixes.

≔⟦§θι¹⟧ζ

Form a "fraction" of the current element.

F⮌…θι

Loop over the preceding elements.

≔⁺⁺⊟ζ×ζκζζ

Invert the fraction and add on the element. This is some decidedly tricky coding. The old denominator is popped from the fraction, leaving behind the old numerator as a list of one element. This is vectorised multiplied by the element and added to the denominator, thus making a list of just the new numerator. The old numerator, still in its list, is then list concatenated to it, where it becomes the new denominator.

¿¬›§ζ¹ηP⪫ζ/

If the denominator is still small enough, overprint the previous fraction (if any) with the current fraction.

\$\endgroup\$
2
\$\begingroup\$

R, 88 80 bytes

function(x,y,`~`=cbind,z=1:0~0:1){for(i in x)z=z[,1]*i+z[,2]~z;z[,z[2,]<=y][,1]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Haskell, 70 69 bytes

x?m=last[y|y<-f x,y!!1<=m]
f(h:t)=[h,1]:[[a*h+b,a]|[a,b]<-f t]
f[]=[]

Try it online!

The relevant function is (?), which takes as input the continued fraction x (as a list of integers) and the maximum denominator m. The output is a list of integers [numerator,denominator].

How?

x?m=            -- x=continued fraction, y=maximum denominator
  last[         -- return the last
    y|y<-f x,   --   convergent of x
    y!!1        --   whose denominator (i.e. second element)
      <=m       --     is at most m
  ]
f                   -- helper function for computing convergents
  (h:t)=            --   h=first number, t=rest of the continued fraction
    [h,1]:          --     the first convergent is h (i.e. h/1)
    [[a*h+b,a]      --     the other convergents are h+b/a (i.e. (a*h+b)/a)
      |[a,b]<-f t]  --       where a/b ranges over the convergents of t
f[]=[]              -- base case for the empty continued fraction
\$\endgroup\$
1
\$\begingroup\$

Retina, 74 bytes

,
¶$%`,
¶
/1¶
+`\d+,(\d+)/(.+)
$.($2*_$1**)/$1
N$r`.*(\d+)
$1
L`.+¶(?!.+/)

Try it online! Takes the continued fraction and denominator on separate lines, but link includes test suite that splits on ; for convenience. Explanation:

,
¶$%`,

Get all prefixes of the continued fraction.

¶
/1¶

Start each prefix with a denominator of 1.

+`\d+,(\d+)/(.+)
$.($2*_$1**)/$1

Calculate each resulting rational number from right to left.

N$r`.*(\d+)
$1

Sort the desired denominator into the list of rational numbers.

L`.+¶(?!.+/)

Output the rational number whose denominator is the largest that does not exceed the desired denominator.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 162 bytes

lambda x,y:min((abs(q-g(*x)),q)for q in[g(*x[:i+1])for i in range(len(x))]if q.denominator<=y)[1]
g=lambda v,*k:v+Fraction(*k and(1,g(*k)))
from fractions import*

Try it online!

-28 bytes thanks to ovs

\$\endgroup\$
3
  • \$\begingroup\$ 179 bytes with a shorter g function. \$\endgroup\$
    – ovs
    Apr 6 at 7:59
  • \$\begingroup\$ 162 bytes by not using a key function and a shorter import. \$\endgroup\$
    – ovs
    Apr 6 at 8:07
  • \$\begingroup\$ @ovs Thanks for the golfs! \$\endgroup\$
    – hyper-neutrino
    Apr 6 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.