23
\$\begingroup\$

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 . Shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Decimal is a radix. Do you mean numbers with fractional parts? \$\endgroup\$ – Marquis of Lorne Jul 22 at 2:25
  • \$\begingroup\$ @MarquisofLorne when I say decimal numbers I'm referring to what people would commonly call decimal numbers (i.e. numbers with digits after the decimal point). Although technically calling them decimal numbers because they are in the decimal system would also be correct \$\endgroup\$ – Daniel H. Jul 22 at 11:22
  • 1
    \$\begingroup\$ This reminded me that 22/7 is a well-known rational approximation of pi... And another really good one is 355/113, which is VERY easy to remember if you memorize it as "split 113355 in half and make a fraction with it". (These 2 come from the continued fraction of pi, in case you are wondering) \$\endgroup\$ – RGS Jul 22 at 14:21
  • 2
    \$\begingroup\$ @RGS I actually included the 22/7 example for this very reason \$\endgroup\$ – Daniel H. Jul 22 at 14:25

16 Answers 16

14
\$\begingroup\$

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.


| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Nice find! You can make this a little shorter by currying the function: Try it online! \$\endgroup\$ – ovs Jul 22 at 18:25
  • \$\begingroup\$ @ovs Thanks! I didn’t even know that is an option in Code Golf. \$\endgroup\$ – David Foerster Jul 22 at 20:46
13
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 3
    \$\begingroup\$ You can make this a little shorter and lot faster with min. \$\endgroup\$ – ovs Jul 22 at 7:29
  • \$\begingroup\$ @ovs I totally missed that, thanks for pointing out! \$\endgroup\$ – Surculose Sputum Jul 22 at 8:43
10
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • 7
    \$\begingroup\$ Welcome to the site, and nice first answer! I'd recommend you check out our Tips for golfing in Python in order to find some neat golfing tricks \$\endgroup\$ – caird coinheringaahing Jul 21 at 16:49
  • 1
    \$\begingroup\$ Here some more improvements by putting the duplicated code in for(2) loop: 135 bytes. PS: tips for golfing in 'all languages' might also be interesting to read through. And great first answer! Welcome. \$\endgroup\$ – Kevin Cruijssen Jul 21 at 17:10
  • 1
    \$\begingroup\$ for _ in[1]*2 basically means to loop twice without using the _. A more readable alternative with the same byte-count in this case could be for q in[0,1]. The [1]*2 will basically make the list [1,1]. And then the for _ in[1,1] will loop over this. There might be a shorter way to execute the code twice perhaps, but I'm not too skilled with Python. I know exec("some_code;"*2) would work for one-liners, but I don't think it will work for the multiple indented lines in this case. \$\endgroup\$ – Kevin Cruijssen Jul 21 at 17:35
  • 1
    \$\begingroup\$ You can get rid of the second for loop using r=round(...) instead of int(...). z can starts at 1, since the error cannot exceed 1. Try it online! \$\endgroup\$ – Surculose Sputum Jul 22 at 0:33
  • 2
    \$\begingroup\$ @Third-party'Chef' I don't think you can remove abs, since r/i can be greater than x. For example, with test 1.19, 8 | 6/5, your solution returns 4/3. \$\endgroup\$ – Surculose Sputum Jul 22 at 6:33
7
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

Charcoal, 31 bytes

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

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

Nθ                              Input decimal as a number
        N                       Input maximum denominator
       E                        Map over implicit range
                κ               Current index (0-indexed)
               ⊕                Increment (i.e. 1-indexed)
             ×                  Multiplied by
              θ                 Input decimal
         ⌊⁺·⁵                   Round to nearest integer
      E                         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:

NθFNF⊕⌈×θ⊕ι⊞υ⟦↔⁻θ∕κ⊕ι⊕ικ⟧I⊟⌊υ/I⊟⌊υ

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

Nθ

Input the decimal.

FN

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

F⊕⌈×θ⊕ι

Loop until the nearest numerator above.

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

Save the fraction difference and the denominator and numerator.

I⊟⌊υ/I⊟⌊υ

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

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

-4 bytes thanks to DomHastings

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

Try it online!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice answer! You can save 4 bytes using $- instead of $n (negates need for int) and using ; as the delimeter for your final s///: Try it online! \$\endgroup\$ – Dom Hastings Jul 24 at 15:44
  • \$\begingroup\$ Thanks, I forgot these tips \$\endgroup\$ – Nahuel Fouilleul Jul 24 at 16:17
3
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice! I saw you'd made an R answer so I didn't want to look at it until I'd tried myself. But I didn't think of round so my best attempt was 75 bytes. Well done. \$\endgroup\$ – Dominic van Essen Jul 25 at 8:21
  • \$\begingroup\$ -1 byte by swapping which.min() for order()[1] \$\endgroup\$ – Dominic van Essen Jul 25 at 8:22
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ i don't understand the role of 1+. ⊃∘⍋ is the index of the smallest, right? so when we add 1 to the whole array, shouldn't ⊃∘⍋ remain the same? \$\endgroup\$ – ngn Jul 22 at 14:29
  • \$\begingroup\$ if leading spaces are ok: ⌊.5+ -> 0⍕ \$\endgroup\$ – ngn Jul 22 at 14:37
  • \$\begingroup\$ @ngn Try the test case starting with 0.255... with 20. If you don't 1+, you get 5/20 due to floating point errors that are big enough that APL treats them as different even with CT. \$\endgroup\$ – Bubbler Jul 22 at 14:42
  • \$\begingroup\$ yeah, i saw that, but aren't rounding errors generally considered acceptable in golfing? \$\endgroup\$ – ngn Jul 22 at 14:49
  • \$\begingroup\$ (⊃∘⍋1+|⍨⌊⊢-|⍨) -> (⊃∘⍋1+|⌊⊣-|)⍨ \$\endgroup\$ – ngn Jul 22 at 15:00
2
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ugh, that's twice this week that someone's based their answer on an answer after mine that uses the same algorithm that mine does... how can I improve my explanations? \$\endgroup\$ – Neil Jul 23 at 10:28
  • 2
    \$\begingroup\$ @Neil I think one reason is that Python is way more readable than Charcoal for most people. :) A trick that might be useful is to include a TLDR at the top about the answer's big idea, since a lot of the time that's all people need/care about. E.g. when I skim through your answer, I'm mostly interested in the algorithm rather than the specific Charcoal commands, and thus I simply skip all the code block. The "loop through all denominator..." sentence is the most telling to me, yet it's buried in the middle of all the hard-to-understand Charcoal stuff. \$\endgroup\$ – Surculose Sputum Jul 27 at 15:00
1
\$\begingroup\$

Wolfram Language (Mathematica), 60 bytes

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

Try it online!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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]
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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...

| improve this answer | |
\$\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.