Cleaning up decimal numbers

Question

Background

Sometimes in calculus you're expected to calculate the sum of an infinite series. Sometimes these series are very friendly, like a geometric series, but add anything else onto it and it can quickly get complicated to solve by hand.

Sometimes I like to be lazy - a lot of sums can be found simply by adding the first few terms then making an approximation. Say the sum of the first ten terms is 0.199999983, and the future terms are approaching zero. We can say with a fair degree of certainty that our final answer will be 0.2, or 1/5.

The Challenge

Given a decimal number and an integer as inputs, calculate the best (fully simplified) fractional approximation of the decimal number for all fractions up to a denominator of the given integer. The best fractional approximation will be that which is closest to the decimal number in absolute value.

You may take these inputs any way you like and you may output the numerator and denominator any way you like. The numerator and denominator must always be integers, and you may assume we will deal with only positive numbers because adding a negative sign is trivial.

Test Cases

Input | Output

1.21, 8 | 6/5

3.14159265359, 1000000 | 3126535/995207

19.0, 10000000 | 19/1

3.14159265359, 12 | 22/7

2.7182818, 100 | 193/71

0.8193927511, 22 | 9/11

0.2557463559, 20 | 1/4

0.2557463559, 100 | 11/43

0.0748947977, 225 | 14/187

Scoring

This is code-golf. Shortest code wins!

Answer 1

Python 3, 66 61 bytes

lambda x:Fraction(x).limit_denominator
from fractions import*

Try it online!

The above function takes a floating point number and returns a bound function Fraction.limit_denominator which, in turn, takes the upper bound for the denominator to return a simplified, approximated fraction as requested.

As you can tell, I’m more of an API reader than a golfer.

---

• minus 5 bytes thanks to ovs

Answer 2

Python 3.8 (pre-release), 77 71 bytes

-6 bytes thanks to @ovs !

lambda x,n:min([abs(x-(a:=round(x*b))/b),a,b]for b in range(1,n+1))[1:]

Try it online!

Simply try all denominators from 1 to n, saving all results into a list where each element has the form [error, numerator, denominator]. By taking the min of the list, the fraction with the smallest error is selected.

Answer 3

Python 2, 168, 135, 87 bytes

z=i=1
def f(x,y):exec"r=round(x*i);q=abs(r/i-x)\nif q<z:z=q;t=r;u=i\ni+=1;"*y;print t,u

Try it online!

Thank you all for your recommendations on my first golf!

Answer 4

05AB1E, 11 bytes

î*LãΣ`/¹α}н

Try it online or verify all test cases (except for the two 1000000 test cases, which take too long).

Explanation:

î          # Ceil the (implicit) input-decimal
 *         # Multiply it by the (implicit) input-integer
  L        # Pop and push a list in the range [1, ceil(decimal)*int]
   ã       # Create all possible pairs of this list by taking the cartesian product
    Σ      # Sort this list of pairs by:
     `     #  Pop and push both values separated to the stack
      /    #  Divide them by one another
       ¹α  #  Get the absolute difference with the first input-decimal
    }н     # After the sort: leave only the first pair
           # (after which it is output implicitly as result)

Answer 5

Python 3.8, 169 bytes

Maybe the reason why there was no submissions using Farey sequences is that the code appears rather lengthy.

In short, every proper fraction \$\frac{m}{k}\$ in lowest terms appears in Farey sequence of order \$d\$ if and only if \$k\le d\$.
Farey sequences are constructed by taking mediant of neighboring terms of lower order: \$\left(\frac ab,\frac cd\right)\to\frac{a+c}{b+d}\$, starting from \$\left(\frac 01,\frac 11\right)\$. And the target number is within one of the intervals \$\left[\frac ab,\frac{a+c}{b+d}\right]\$, \$\left[\frac{a+c}{b+d},\frac cd\right]\$, then we take the interval as a current one.

So the algorithm is:

1. Take \$\left(\frac ab,\frac cd\right):=\left(\frac 01,\frac 11\right)\$.
2. Take \$\frac{m}{k}:=\frac{a+c}{b+d}\$ and compare with target.
3. If \$\frac{m}{k}>\$ target, replace \$\frac{a}{b}\$ by \$\frac{m}{k}\$,
4. Else replace \$\frac{c}{d}\$ by \$\frac{m}{k}\$.
5. If the next denominator \$b+d\$ is no more than denominator limit, repeat from 2.
6. Else return nearest from \$\frac ab,\frac cd\$ to the target.

def f(e,n,g,j):
	if n==0:return e,1
	x=[(0,1),(1,1)]
	while True:
		(a,b),(c,d)=x
		if b+d>j:break
		m,k=a+c,b+d
		x[m*g>n*k]=(m,k)
	m,k=x[2*n/g-a/b>c/d]
	return m+e*k,k

Try it online!

Eats (entire_part,proper_numerator,proper_denominator,denominator_limit) and produces (numerator,denominator), like

>>> f(3,141592653589793,10**len('141592653589793'),57)
(179, 57)

P.S. Recursive version is nothing but shorter, even with all whitespace removed:

f=(lambda e,n,g,j,a=0,b=1,c=1,d=1:
   n and(
       b+d>j and(lambda x,y:(x+e*y,y))(*([(a,b),(c,d)][2*n/g-a/b>c/d]))
       or((m:=a+c)*g>n*(k:=b+d))and f(e,n,g,j,a,b,m,k)or f(e,n,g,j,m,k,c,d)
       )or(e,1)
   )

Try it online!

Answer 6

Charcoal, 31 bytes

Ｎθ⪫…⮌⌊ＥＥＮ⌊⁺·⁵×θ⊕κ⟦↔⁻θ∕ι⊕κ⊕κι⟧²/

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

Ｎθ                              Input decimal as a number
        Ｎ                       Input maximum denominator
       Ｅ                        Map over implicit range
                κ               Current index (0-indexed)
               ⊕                Increment (i.e. 1-indexed)
             ×                  Multiplied by
              θ                 Input decimal
         ⌊⁺·⁵                   Round to nearest integer
      Ｅ                         Map over results
                      ι         Current numerator
                     ∕          Divided by
                       ⊕κ       Current denominator
                    θ           Input decimal
                  ↔⁻            Absolute difference
                         ⊕κ     Current denominator
                           ι    Current numerator
                 ⟦          ⟧   Make into list
     ⌊                          Take the minimum (absolute difference)
    ⮌                           Reverse the list
   …                         ²  Take the first two entries
  ⪫                           / Join with literal `/`
                                Implicitly print

I'm not 100% sure that the algorithm is correct, so just in case, here's a 34-byte brute-force solution:

ＮθＦＮＦ⊕⌈×θ⊕ι⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧Ｉ⊟⌊υ/Ｉ⊟⌊υ

Try it online! Link is to verbose version of code. Very slow, so test case is limited to a denominator of 1000. Explanation:

Ｎθ

Input the decimal.

ＦＮ

Loop over the possible denominators (except 0-indexed, so all of the references to the loop variable have to be incremented).

Ｆ⊕⌈×θ⊕ι

Loop until the nearest numerator above.

⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧

Save the fraction difference and the denominator and numerator.

Ｉ⊟⌊υ/Ｉ⊟⌊υ

Print the numerator and denominator of the fraction with the minimum difference.

Answer 7

Japt v2.0a0 -g, 15 bytes

mc ×õ ï ñ@ÎaXr÷

Try it

mc ×õ ï ñ@ÎaXr÷     :Implicit input of array U
m                   :Map
 c                  :  Ceiling
   ×                :Reduce by multiplication
    õ               :Range [1,result]
      ï             :Cartesian product with itself
        ñ           :Sort by
         @          :Passing each pair X through the following function
          Î         :  First element of U
           a        :  Absolute difference with
            Xr÷     :  X reduced by division
                    :Implicit output of first pair

Answer 8

Zig 0.6.0, 149 bytes

fn a(e:f64,m:f64)[2]f64{var n:f64=1;var d=n;var b=d;var c=b;while(d<m){if(n/d>e)d+=1 else n+=1;if(@fabs(n/d-e)<@fabs(b/c-e)){b=n;c=d;}}return.{b,c};}

Try it

Formatted:

fn a(e: f64, m: f64) [2]f64 {
    var n: f64 = 1;
    var d = n;
    var b = d;
    var c = b;
    while (d < m) {
        if (n / d > e) d += 1 else n += 1;
        if (@fabs(n / d - e) < @fabs(b / c - e)) {
            b = n;
            c = d;
        }
    }
    return .{ b, c };
}

Variable declarations are annoying.

Answer 9

Perl 5 -p -MList::Util=min, 65, 61 bytes

-4 bytes thanks to DomHastings

/ /;$_=min map abs($`-($-=.5+$_*$`)/$_)." $-/$_",1..$';s;.* ;

Try it online!

Answer 10

R, 61 60 bytes

With a byte saved by Dominic van Essen.

function(x,d,n=round(1:d*x))c(m<-order((x-n/1:d)^2)[1],n[m])

Try it online!

Answer 11

Jelly, 11 bytes

Ċ×⁹p÷/ạ¥Þ⁸Ḣ

A dyadic Link accepting the decimal [evaluated as a float] on the left and the denominator limit on the right which yields a pair [numerator, denominator] representing the simplified fraction.

Try it online! Or see the test-suite (big denominator limit cases removed due to inefficiency.)

How?

Ċ×⁹p÷/ạ¥Þ⁸Ḣ - Link: v, d
Ċ           - ceil (of the decimal value, v)
 ×⁹         - multiplied by chain's right argument (denominator limit, d)
   p        - Cartesian power (d) -> all pairs [[1,1],...,[1,d],[2,1],...,[Ċ×⁹,d]]
                  (note that any pair representing a non-simplified fraction is to
                   the right of its simplified form)
        Þ   - (stable) sort by:
       ¥    -   last two links as a dyad:
     /      -     reduce by:
    ÷       -       division (i.e. evaluate the fraction)
      ạ  ⁸  -     absolute difference with the chain's left argument (v)
          Ḣ - head

Answer 12

APL (Dyalog Unicode), 26 bytes

⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣

Try it online!

A dyadic tacit function that takes the decimal number on its left and the max denominator on its right, and gives a 2-element vector of [denominator, numerator].

How it works

⌊.5+(⊃∘⍋1+|⍨⌊⊢-|⍨)∘÷∘⍳×1,⊣  ⍝ Left: x, Right: d
                  ∘÷∘⍳      ⍝ v←[1, 1/2, ..., 1/d]
    (          |⍨)          ⍝ Remainder of x divided by each of v
          |⍨⌊⊢-             ⍝ Min distance from x to some integer multiple of v
        1+                  ⍝ Add 1 to treat close enough numbers as same
                            ⍝ Otherwise it gives something like 5/20 due to FP error
     ⊃∘⍋                    ⍝ D←The index of minimum (the optimal denominator)
                      ×1,⊣  ⍝ Exact fraction (D,Dx)
⌊.5+                        ⍝ Round both

Answer 13

Io, 78 bytes

Port of Surculose Sputum's answer.

method(x,y,Range 1to(y)map(a,list((x-(b :=(a*x)round)/a)abs,b,a))min slice(1))

Try it online!

Io, 93 bytes

method(x,y,list(((q :=(r :=Range 0to(y)map(a,(x-(a*x)round/a)abs))indexOf(r min))*x)round,q))

Try it online!

Explanation (ungolfed):

method(x, y,                   // Take two operands
    r := Range 0 to(y) map(a,  // Map in range 0..y (set to r):
        (x-(a*x)round/a)abs    //     |x-round(a*x)/a|
    )                          //     (Aka find the appropriate numerator)
    q :=r indexOf(r min)       // Set q as the 0-index of the smallest number of r
    list((q*x)round,q)         // Output [numerator,denominator]
)                              // End function

Answer 14

Wolfram Language (Mathematica), 60 bytes

(t=s=1;While[Denominator[s=Rationalize[#,1/t++]]<#2,j=s];j)&

Try it online!

Answer 15

Julia, 66 bytes

r(x,m)=minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

or

(x,m)->minimum((n=Int(round(x*d));(abs(x-n/d),n//d)) for d=1:m)[2]

Answer 16

R, 75 bytes

function(x,d)c((n=rep(0:1,e=d)+(1:d*x)%/%1)[f<-order((x-n/1:d)^2)[1]],f%%d)

Try it online!

Not a competitive answer as it's already beaten by Kirill, but posting for fun anyway.

I didn't think of the round() function, so this approach rounds down & then up to generate a double-length list of candidate numerators, and then finds the index of the closest fraction. Since the index might be in the second (rounded-up) part of the list, the denominator is the index mod the length of the single-length list.

I think it's fair to conclude that the round() function indeed serves a useful role...