Convert a decimal to a fraction, approximately

Question

Take the decimal number \$0.70710678\$. As a fraction, it'd be \$\frac{70710678}{100000000}\$, which simplifies to \$\frac{35355339}{50000000}\$. If you were to make the denominator \$1\$, the closest fraction is \$\frac{1}{1}\$. With \$2\$, it'd be \$\frac{1}{2}\$, and with \$3\$ it's \$\frac{2}{3}\$. Because \$0.\bar{6}\$ is closer to \$0.70710678\$ than \$\frac{3}{4}\$ or \$\frac{4}{5}\$, it would still be the closest with a maximum denominator up to (and including) \$6\$.

Task

There are two inputs: a decimal, and a maximum denominator.

The first input consists of a number \$n\$ as input, where \$0\le n<1\$, and the fractional part is represented with a decimal (although not necessarily using base 10). This can be represented as a floating point number, an integer representing a multiple of \$10^{-8}\$ (or some other sufficiently smaller number), a string representation of the number, or any other reasonable format.

The second input is an integer \$n\ge1\$, also taken in any reasonable format.

The output should be a fraction, with a denominator \$d\le n\$, where \$n\$ is the second input. This should be the closest fraction to the inputted decimal that is possible with the restrictions placed on the denominator. If there are multiple which are equally close (or equal to the inputted number), the one with the smallest denominator should be chosen. If there are two with the same denominator which are equidistant, either are acceptable.

The outputted fraction can be represented in any reasonable format, as long as it consists of a numerator and denominator, both being natural numbers.

Test cases

0.7         4   ->   2 / 3
0.25285     15  ->   1 / 4
0.1         10  ->   1 / 10
0.1         5   ->   0 / 1
0.68888889  60  ->  31 / 45
0.68888889  30  ->  20 / 29
0.0         2   ->   0 / 1
0.99999999  99  ->   1 / 1

Other

This is code-golf, shortest answer in bytes per language wins!

Answer 1

Scratch 3.0, 45 blocks/254 bytes

As SB Syntax:

define(n)(d)
set[A v]to(0
set[D v]to(d
set[i v]to(0
repeat((n)+(1
set[j v]to(0
repeat((n)+(1
set[r v]to((i)/(j
if<(D)>([abs v]of((r)-(D)))>then
set[A v]to(join(i)(join(/)(j
set[D v]to([abs v]of((r)-(D
end
set[j v]to((j)+(1
end
set[i v]to((i)+(1
end
say(A

Try it on Scratch!

Just wouldn't be right if I didn't do this in Scratch.

Explained

define(n)(d) // Define an empty name function with parameters `n` (the denominator) and `d` (the decimal to fractionify)
set[D v]to(d // This will store the current absolute difference between potential fraction and actual decimal
set[i v]to(0 // outer-cartesian-loop variable
repeat((n)+(1
set[j v]to(0 // inner-cartesian-loop variable
repeat((n)+(1 // simulate cartesian product of range(0, n+1) and range(0, n+1)
set[r v]to((i)/(j // divide i / j
if<(D)>([abs v]of((r)-(D)))>then // if the difference between (i/j) and d is smaller than the current smallest difference
set[A v]to(join(i)(join(/)(j // update answer and difference
set[D v]to([abs v]of((r)-(D
end
set[j v]to((j)+(1
end
set[i v]to((i)+(1
end
say(A // output answer

Answer 2

Husk, ¹² 10 bytes

◄oa-⁰´×/ŀ→

Try it online!

≠ is absolute difference, but doesn't seem to work for floats. So oa- is used.

-2 bytes from Leo.

Explanation

◄oa-⁰´×/ŀ→ Inputs: decimal → ⁰, max denominator → implicit
        ŀ→ range 0..denominator
     ´×/   convert all possible pairs to fractions
◄o         min by
  a-⁰      absolute difference with the decimal

Answer 3

05AB1E, 10 bytes

ÝD¦âΣ`/α}¬

Try it online!

Explanation

Ý          # [0 .. input]
 D         # Duplicate
  ¦        # Tail -> [1 .. input]
   â       # Cartesian product
    Σ   }  # Sort by
       α   # Absolute difference between
           # Input 2
     `/    # and numerator / denominator
         ¬ # Head

Answer 4

J, 21 bytes

(0{]/:&,|@-)%/~@i.@>:

Try it online!

Takes float as left input, max denominator as right input.

• %/~@i.@>: Creates "division table" for all pairs 0 to max denominator.
• |@- Elementwise differences between those table values and the target float.
• ]/:&, Sort the table /: according to those differences after flattening both &,.
• 0{ Return the first item in the sorted list.

Answer 5

Jelly, 9 bytes

Żpḷ÷/ạ¥ÞḢ

Try it online!

Verify all test cases

Note that this selects the fraction with the smallest numerator, and I'm not completely sure if it's always also the one with the smallest denominator.

Takes the maximum denominator as the first argument and the float as the second argument.

Explanation

Żpḷ÷/ạ¥ÞḢ   Main dyadic link, taking m and x
Ż           Range [0..m]
 p          Cartesian product with
  ḷ         m, implicitly converted to the range [1..m]
       Þ    Sort by
      ¥     (
   ÷/         Divide the two numbers
     ạ        Absolute difference with x
      ¥     )
        Ḣ   Head

Answer 6

JavaScript (ES7), 64 bytes

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

v=>g=(d,e)=>d?g(d-1,(E=((q=v*d+.5|0)/d-v)**2)>e?e:(r=[q,d],E)):r

Try it online!

Commented

v =>                     // outer function taking the float value v
g = (d, e) =>            // inner recursive function taking the maximum denominator d
                         // and the current minimum error e, initially undefined
  d ?                    // if d is not equal to 0:
    g(                   //   do a recursive call:
      d - 1, (           //     decrement d
        E = (            //     compute the new error E = (q / d - v)²
          (q = v * d     //     where q is round(v * d)
               + .5 | 0) //
          / d - v        //
        ) ** 2           //     it's shorter to square than to use Math.abs()
      )                  //
      > e ?              //     if E is greater than e (always false if e is still
                         //     undefined):
        e                //       pass e unchanged
      :                  //     else:
        (r = [q, d], E)  //       save the new result [q, d] in r and pass E
    )                    //   end of recursive call
  :                      // else:
    r                    //   return the final result

Answer 7

Python 3, 97 90 bytes

def f(n,k,a=[1]):
 while k:p=round(n*k);j=abs(p/k-n);a=[a,(j,p,k)][j<=a[0]];k-=1
 return a

Try it online!

round(n*k) gets the closest numerator for a given denominator k. abs(p/k-n) calculates the absolute value between this fraction and the input fraction n. If this is the best option so far, then update the answer accordingly.

Outputs three values: the absolute difference, the numerator and the denominator respectively.

thanks to Noodle9 for -7 bytes

Answer 8

PowerShell, 83 bytes

param($n,$d)1..$d|%{0..($x=$_)|%{@{n=$_;d=$x}}}|sort{[Math]::Abs($_.n/$_.d-$n)}-t 1

Try it online!

Answer 9

Excel, 72 bytes

=LET(a,SEQUENCE(B1),x,ROUND(A1*a,),INDEX(SORTBY(x&"/"&a,ABS(x/a-A1)),1))

Answer 10

Wolfram Language, 62 57 bytes

-3 bytes thanks to J42161217.

MinimalBy[Join@@Array[Divide,{#,#}+1,0],a|->Abs[a-#2],1]&

Try it online! (uses \[Function] rather than |->, as TIO doesn't have the most recent version of the language)

Does the brute-force method of generating every possible fraction and taking the one closest to the given number. I previously had a solution using Convergents, but it failed for inputs like 0.1 where, because of the language accounting for inexact numbers, the closest fraction wouldn't appear in the list.

Answer 11

Vyxal, 69 bits^v2, 8.625 bytes

ʁ:ḢẊµƒ/⁰ε;h

Try it Online!

A port of the 05AB1E answer updated to 2.6+ and vyncoded.

Explained

ʁ:ḢẊµƒ/⁰ε;h
ʁ:         # Push two copies of the range [0, input)
  Ḣ        # on one of those copies, remove the first element
   Ẋ       # Take the cartesian product of these two lists
    µ...;  # And sort this by:
     ƒ/⁰ε  # the absolute difference between the second input and the item reduced by division
         h # output the first item

Answer 12

JavaScript (V8), 81 bytes

n=>k=>eval('for(a=0,b=M=1;b<=k;(m=a/b<n?n-a++/b:a/b++-n)<M&&[R=P,M=m])P=[a,b];R')

Try it online!

Maybe there are edge cases which failed due to floating point errors. But it at least pass all testcases given by OP.

Answer 13

JavaScript (ES6), 63 bytes

c=>f=(d,M)=>d?f(d-1,M>(N=(.5-d*c%1)**2)?M:(s=d,N)):[c*s+.5|0,s]

Like this answer, expects (value)(max_denominator), and returns [numerator, denominator].

Here's how it works:

c=>                          // the decimal - this will not change
  f=(                        // the inner recursive function
    d,                       // the max denominator. We will decrement this to loop
    M                        // the "error" (with a twist)
  )=>                        
    d?                       // if d is nonzero, we're still recursing
      f(d-1,                 // call f with the new denominator we're testing
        M>                   // the bigger M is, the closer d*c is to an integer
          (N=                // we'll test the error and save it in N in case we need it
            (.5-d*c%1)**2    // the error (with the twist); the closer d*c to an integer, the
                             // closer d*c%1 to 0 or 1, the closer .5-d*c%1 to .5, the bigger
                             // (.5-d*c%1)**2 is. This means; bigger "error" is better
          )
          ?M                 // if M is bigger than the newly checked error, continue with M
          :(                 // otherwise,
            s=d,             // save that denominator in s,
            N                // continue with the new error (that we saved in N)
          )
        )
    :                        // if d is zero, we've checked all denominators so we're done
    [c*s+.5|0,               // return the numerator (which is just c*s rounded to the nearest integer)
    s]                       // and the denominator, which we saved in s

Answer 14

R, 61 bytes

function(n,d,a=round(n*1:d))c(a[i<-which.min((a/1:d-n)^2)],i)

Try it online!

Answer 15

Charcoal, 27 bytes

ＮθＦＮＦ⁺²ι⊞υ⟦↔⁻∕κ⊕ιθκ⊕ι⟧Ｉ✂⌊υ¹

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

Ｎθ

Input n.

ＦＮ

Input the maximum denominator and loop up to it. (The actual denominator is 1 more than the loop index.)

Ｆ⁺²ι

Loop over the possible numerators.

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

Calculate the error and save the numerator and denominator with it.

Ｉ✂⌊υ¹

Output the numerator and denominator with the smallest error (in the case of a tie, the smallest numerator wins).

Answer 16

JavaScript (V8), 93 bytes

(d,m)=>eval("for(i=1,b=m;i<=m;i++)n=Math.round(d*i),w=Math.abs(d-n/i),w<b?[b=w,x=[n,i]]:0;x")

Try it online!

Explanation:

Fairly straighforward approach. Most of the work is done by a for loop, wrapped in an eval statement. This saves bytes, as it's shorter than wrapping it in {} (which requires return).

During the for loop (all iterations are denominators from 1 to m), four things happen:

• n is set to the closest numerator
• w is set to the distance between the fraction and the d (the first number)
• w is compared with the previous best, b (initially Infinity)
• If w is less than b, b takes w's value and x (the output) becomes the outputted fraction

Answer 17

Haskell, 100 bytes

u=10^8
a#b|b!!0<a!!0=b|1>0=a
n!m=tail$foldl1(#)[[min o$u-o,div(n*d+o)u,d]|d<-[1..m],let o=n*d`mod`u]

Try it online!

• input as 8 digits of the decimal part of n.
• output a [ numerator, denominator ] list.

a#b selects a or b (which are [distance to closest 10^8 multiple, numerator , denominator] ) based on minimum distance.

n!m computes every [dist, num, den] from 1 to m ,
then finds closest fraction folding by # and return only [num,den]

Answer 18

Julia 1.7, 37 bytes

x|n=argmin(y->(x-y)^2,(0:n).//(1:n)')

Attempt This Online!

argmin(f, domain) needs julia 1.7 or later

Answer 19

Thunno 2 h, 10 bytes

LDḣṖÞẸ/¹-A

Attempt This Online!

Port of user100947's 05AB1E answer.

Explanation

LDḣṖÞẸ/¹-A  # Implicit input
LD          # Push [0..input) and duplicate
  ḣṖ        # Cartesian product of [0..input) with [1..input)
    Þ       # Sort by:
     Ẹ/     #  Dump and divide
       ¹-A  #  Absolute difference with second input
            # Implicit output of first item