25
\$\begingroup\$

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 , shortest answer in bytes per language wins!

\$\endgroup\$
4
  • 4
    \$\begingroup\$ Can we output only 0 or 1 when the denominator would be 1? \$\endgroup\$ – Leo Mar 24 at 4:34
  • 4
    \$\begingroup\$ @Leo That seems reasonable enough, sure \$\endgroup\$ – Redwolf Programs Mar 24 at 4:34
  • 1
    \$\begingroup\$ Your test case for 0.1, 5 as inputs you list both 0/1 and 1/5 as acceptable outputs. This seems to contradict the rules that say "If there are multiple which are equally close ... the one with the smallest denominator should be chosen". My reading is that only 0/1 is an acceptable answer for this test case. \$\endgroup\$ – Brian J Mar 24 at 17:53
  • 1
    \$\begingroup\$ @BrianJ Right you are...I'm not even sure if such a case does exist now that I think about it. \$\endgroup\$ – Redwolf Programs Mar 24 at 17:54

18 Answers 18

12
\$\begingroup\$

Scratch 3.0, 45 blocks/254 bytes

enter image description here

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
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Wasn't expecting scratch! \$\endgroup\$ – Clvckl3s Mar 24 at 22:26
9
\$\begingroup\$

Husk, 12 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
\$\endgroup\$
2
6
\$\begingroup\$

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
\$\endgroup\$
0
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ The functionality is built into the standard library as Fraction.limit_denominator. I'm not sure if it would save bytes, though. \$\endgroup\$ – dan04 Mar 24 at 18:03
  • 1
    \$\begingroup\$ @dan04 I see. I didn't know about this built-in at the time of writing this answer. And looks like this answer already made use of it too. :) \$\endgroup\$ – Manish Kundu Mar 24 at 18:08
4
\$\begingroup\$

Excel, 72 bytes

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

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 59 bytes \$\endgroup\$ – ZaMoC Mar 24 at 9:56
  • 1
    \$\begingroup\$ @J42161217 Yes. \$\endgroup\$ – DanTheMan Mar 24 at 22:19
  • \$\begingroup\$ 43 bytes \$\endgroup\$ – att Apr 6 at 16:35
4
\$\begingroup\$

Vyxal, 11 10 bytes

ʁ:ḢẊµɖ⁰ε;h

Try it Online!

A port of the 05AB1E answer.

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
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

PowerShell, 83 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 27 bytes

NθFNF⁺²ι⊞υ⟦↔⁻∕κ⊕ιθκ⊕ι⟧I✂⌊υ¹

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

Nθ

Input n.

FN

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

F⁺²ι

Loop over the possible numerators.

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

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

I✂⌊υ¹

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

\$\endgroup\$
3
  • \$\begingroup\$ This answer seems to give the wrong output for 0.1,5 (it produces 1/5, the testcases say the right answer is 0/1) \$\endgroup\$ – pppery Mar 29 at 3:52
  • \$\begingroup\$ Also 0.0,2. This answer gives 1/2, the testcases say the right answer is 0/1 \$\endgroup\$ – pppery Mar 29 at 3:54
  • \$\begingroup\$ @pppery Ugh, I was so fixated on a non-zero denominator that I forgot that the numerator could be zero, which actually saves me a byte... \$\endgroup\$ – Neil Mar 29 at 9:40
2
\$\begingroup\$

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
\$\endgroup\$
2
  • 3
    \$\begingroup\$ You shouldn't be answering your own questions so quickly, the current consensus is to wait for other answers. \$\endgroup\$ – Noodle9 Mar 24 at 10:25
  • 1
    \$\begingroup\$ @Noodle9 Ah, sorry, I didn't know that. Thanks! (I did wait until there were some other answers which used the same approach as me, but I'll wait longer in the future) \$\endgroup\$ – Redwolf Programs Mar 24 at 13:10
2
\$\begingroup\$

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]

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

Julia, 42 bytes

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

Try it online!

\$\endgroup\$

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.