Truncate continued fractions

Question

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 code-golf 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

Answer 1

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]

Answer 2

J, ²⁵ 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.

Answer 3

Wolfram Language (Mathematica), 47 bytes

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

Try it online!

-25 bytes from @att

Answer 4

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

Answer 5

Charcoal, 38 bytes

ＦＬθ«≔⟦§θι¹⟧ζＦ⮌…θι≔⁺⁺⊟ζ×ζκζζ¿¬›§ζ¹ηＰ⪫ζ/

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

ＦＬθ«

Loop over the prefixes.

≔⟦§θι¹⟧ζ

Form a "fraction" of the current element.

Ｆ⮌…θι

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.

¿¬›§ζ¹ηＰ⪫ζ/

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

Answer 6

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!

Answer 7

Haskell, ⁷⁰ 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

Answer 8

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.

Answer 9

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