22
\$\begingroup\$

When you convert a fraction to a decimal number and you want to store that number, you often have to round it, because you only want to use a certain amount of memory. Let's say you can only store 5 decimal digits, then 5/3 becomes 1.6667. If you can store only 2 decimal digits it will be 1.7 (now assuming that it is always between 0 and 9.99...).

If you now try to reverse that process with 1.7 and you want to get your fraction back, that can be difficult, since you know that 1.7 is only a rounded number. Of course you can try 17/10 but that is rather an 'ugly' fraction compared to the 'elegant' 5/3.

So the goal is now finding the fraction a/b with the least denominator b, that results in the rounded decimal number when correctly rounded.

Details

The input contains a string with a number of 1 up to 5 digits that is between 0 (including) and 10 (not including) with a '.' after the first digit. Let's say n denotes the number of digits. The output must be a list/array of two integers [numerator, denominator] or a rational datatype (you can create your own or use built-in) where the numerator is non-negative and the denominator is positive. The fraction numerator/denominator must be equal to the input when correctly rounded to n digits (which means n-1 digits after the decimal point).

Restriction: only one loop statement allowed. This means that you can use only one single looping statement (like for or while or goto etc. as well as functional loops like map or fold that apply code to every element of a list/array) in your whole code, but you are free to 'abuse' it or use recursion etc.

You should write a function. If your language does not have functions (or even if it does), you can alternatively assume that the input is stored in a variable (or input via stdin) and print the result or write it to a file. The lowest number of bytes wins.

Rounding

The rounding should follow the 'conventional' rounding rules, i.e. if the last digit that will be cut off is 5 or greater, you will round up, and you will round down for any other cases, so e.g:

4.5494 will result when rounding to

  • 1 digit: 5
  • 2 digits: 4.5
  • 3 digits: 4.55
  • 4 digits: 4.549

Examples

Please include following test cases and other 'interesting' ones:

Input 1.7     Output 5/3
Input 0.      Output 0/1
Input 0.001   Output 1/667
Input 3.1416  Output 355/113
\$\endgroup\$
  • 1
    \$\begingroup\$ But in functional languages there is no such a thing as a loop. Foe example in haskell repeat creates an infinite list of its argument. I t seems to loop but it actually has time complexity of O(1). But i guess sorting each case individually is better than not allowing functional languages. \$\endgroup\$ – proud haskeller Sep 23 '14 at 15:44
  • 2
    \$\begingroup\$ I don't like the current definition of "loop". In Python, for example, for n in numbers: f(g(n)) is equivalent to map(f, map(g, numbers)). The functional version uses map twice, should that really be disallowed? \$\endgroup\$ – flornquake Sep 23 '14 at 16:19
  • 1
    \$\begingroup\$ @MartinBüttner I talked about the case that functional languages would be disallowed because of ambiguity \$\endgroup\$ – proud haskeller Sep 23 '14 at 16:37
  • 1
    \$\begingroup\$ I am sorry that I cannot really contribute to that discussion since my knowledge about functional programming is basically zero. If you have a solution of which you are unsure about whether it complies with the 'rules' please submit it anyway! In the end it is supposed to be a fun and educational challenge! \$\endgroup\$ – flawr Sep 23 '14 at 20:51
  • 2
    \$\begingroup\$ @Dennis No that was unfortunate wording, you can submit it in any form you like, the main idea behind that paragraph was that you should not have a disadvantage if your language takes more bytes for 'reading' the input number. \$\endgroup\$ – flawr Sep 24 '14 at 11:55

14 Answers 14

4
\$\begingroup\$

CJam, 41 40 36 bytes

Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@

Asuumes the input string is stored in Q, which is explicitly allowed by the question. Try it online.

Test cases

$ for d in 1.7 0. 0.001 3.1416; do cjam <(echo "\"$d\":Q;
> Q'./1=,:L0\{;)_Qd*mo_d2$/LmOQd-}g'/@
> "); echo; done
5/3
0/1
1/667
355/113

How it works

Q'./1=,:L  " Count the number of characters after the dot and store it in L.     ";
0\         " Push 0 (denominator) and swap it with L (dummy value).              ";
{          "                                                                     ";
  ;        " Discard the topmost item from the stack (numerator or dummy value). ";
  )        " Increment the denominator.                                          ";
  _Qd*mo   " Multiply a copy by Double(Q) and round.                             ";
  _d2$/    " Cast a copy to Double and it divide it by the denominator.          ";
  LmO      " Round to L digits.                                                  ";
  Qd       " If the result is not Double(Q),                                     ";
}g         " repeat the loop.                                                    ";
./@        " Push a slash and rotate the denominator on top of it.               ";
\$\endgroup\$
15
\$\begingroup\$

T-SQL 254

While T-SQL isn't really suited to this sort of thing, it wa fun to try. The performance gets real bad the higher the denominator. It is limited to a denominator of 1000.

Input is a float variable @

WITH e AS(SELECT *FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)),t AS(SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N FROM e a,e b,e c,e d)SELECT TOP 1concat(n.n,'/',d.n)FROM t d,t n WHERE round(n.n/(d.n+.0),len(parsename(@,1)))=@ ORDER BY d.n,n.n

A breakdown of the query

WITH                                      -- Start CTE(Common Table Expression)
 e AS(                                    --Create a set of 10 rows
   SELECT *
   FROM(VALUES(1),(2),(3),(4),(5),(6),(7),(8),(9),(0))n(n)
 ),
 t AS(                                    
   SELECT ROW_NUMBER()OVER(ORDER BY(SELECT \))N 
   FROM e a,e b,e c,e d                   --Cross join e to produce 1000 numbered rows
 )
SELECT 
  TOP 1                                   --Grab first result
  concat(n.n,'/',d.n)                     --Build output
FROM t d,t n                              --Cross join t against itself for denominator and numerator
WHERE round(
  n.n/(d.n+.0),                           --Force float division with +.0
  len(parsename(@,1))                     --Get rounding length
  )=@                                     --Filter where the rounded result = input
ORDER BY d.n,n.n                          --Order by denominator then numerator
\$\endgroup\$
  • \$\begingroup\$ +1. I love it. I put in 3.14159 and it duly gave me 355/113 \$\endgroup\$ – Tom Chantler Sep 24 '14 at 11:34
  • 1
    \$\begingroup\$ +1 I never expected to see an SQL language here!!! \$\endgroup\$ – flawr Sep 24 '14 at 11:58
  • \$\begingroup\$ @TomChantler I suspect you mean eventually :) \$\endgroup\$ – MickyT Sep 24 '14 at 19:07
  • \$\begingroup\$ @flawr To be honest I didn't think it was going to work .. very brute force method though. \$\endgroup\$ – MickyT Sep 24 '14 at 19:08
12
\$\begingroup\$

Haskell, 62 59

if only the names weren't so long...

import Data.Ratio
f s=approxRational(read s)$50/10^length s

this is a function returning a Rational value.

explanation: the function approxRational is a function which takes a float number and a float epsilon and returns the most simple rational which is in distance epsilon of the input. basically, returns the most simple approximation of the float to a rational in a "forgivable error" distance.

let's exploit this function for our use. for this we will need to figure out what is the area of the floats that round up to the given number. then getting this into the approxRational function will get us the answer.

let's try 1.7, for example. the lowest float that rounds to 1.7 is 1.65. any lower will not round to 1.7. similarly, the upper bound of the floats that round to 1.7 is 1.75.
both limits are the bounds are the input number +/- 0.05. it can be easily shown that this distance is always 5 * 10 ^ -(the length of the input - 1) (the -1 is because there is always a '.' in the input). from here the code is quite simple.

test cases:

*Main> map f ["1.7", "0.001", "3.1416"]
[5 % 3,1 % 667,355 % 113]

unfortunately it doesn't work on "0." because Haskell's parser function doesn't recognize a . at the end of a float. this can be fixed for 5 bytes by replacing read s by read$s++"0".

\$\endgroup\$
  • \$\begingroup\$ It's an interesting function to have. Ordinarily such functions exist for the purpose of finding the best rational approximation to a number in the fewest steps, which is provably accomplished using truncated continued fraction representations. Alternatively, finding a fraction with the lowest denominator is more an academic curiosity. One ordinarily wouldn't expect to find it as a standard library function. \$\endgroup\$ – COTO Sep 23 '14 at 17:22
  • 4
    \$\begingroup\$ @COTO Well, this is Haskell, it is full of academic research. \$\endgroup\$ – proud haskeller Sep 23 '14 at 17:26
7
\$\begingroup\$

Ruby, 127 125 bytes

f=->n{b=q=r=(m=n.sub(?.,'').to_r)/d=10**p=n.count('0-9')-1
b=r if(r=(q*d-=1).round.to_r/d).round(p).to_f.to_s==n while d>1
b}

Defines a function f which returns the result as a Rational. E.g. if you append this code

p f["1.7"]
p f["0."]
p f["0.001"]
p f["3.1416"]

You get

(5/3)
(0/1)
(1/667)
(355/113)

The loop is over denominators. I'm starting with the full fraction, e.g. 31416/10000 for the last example. Then I'm decrementing the denominator, proportionally decrement the numerator (and round it). If the resulting rational rounds to the same as the input number, I'm remembering a new best fraction.

\$\endgroup\$
4
\$\begingroup\$

Mathematica, 49 53 characters

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@

Usage:

Rationalize[ToExpression@#,5 10^(1-StringLength@#)]&@"1.7"

Output:

5/3

Test cases:

input: 1.7     output: 5/3
input: 0.      output: 0
input: 0.001   output: 1/999
input: 3.1416  output: 355/113

The 0.001 case strikes me as odd; as the rationalize function didn't work according to its description, when it didn't find the 1/667 case. It should output the number with the smallest denominator that is within specified bounds.

\$\endgroup\$
  • 2
    \$\begingroup\$ haha I used the exact same solution. too bad in Haskell it's longer. btw, it doesn't look like your solution takes a string as an input as is required by spec. \$\endgroup\$ – proud haskeller Sep 23 '14 at 16:41
  • \$\begingroup\$ Wait, the input was a string? Dang, that means I can pull some stuff out of the code. \$\endgroup\$ – Tally Sep 23 '14 at 16:52
  • \$\begingroup\$ Your output for 0.001 doesn't match the OP because Rationalize isn't under the constraint to minimize the denominator. As I mentioned to proud haskeller, a rational approximation function subject to minimizing the denominator is highly esoteric (in short because it's a lousy and inefficient way to approximate numbers). I ordinarily wouldn't expect it to be a standard library function. \$\endgroup\$ – COTO Sep 23 '14 at 17:28
  • \$\begingroup\$ @COTO According to the docs it does minimise the denominator though. \$\endgroup\$ – Martin Ender Sep 23 '14 at 17:33
  • \$\begingroup\$ @MartinBüttner: It is kind of interesting that it outputs 1/999. 999 becomes the (acceptable) lowest denominator only for an error between roughly 1e-6 and 2e-6. The error bound is clearly 5e-4. So whatever Mathematica is doing in that case, it definitely isn't working to spec. :P \$\endgroup\$ – COTO Sep 23 '14 at 17:54
4
\$\begingroup\$

Python 2.7+, 111 characters

Proof that you can write horrible code in any language:

def f(s):
 t,e,y=float(s),50*10**-len(s),1;n=d=x=0
 while x|y:n,d=n+x,d+y;a=1.*n/d;x,y=a<t-e,a>t+e
 return n,d

Output

>>> [f(s) for s in ("1.7", "0.", "0.001", "3.1416")]
[(5, 3), (0, 1), (1, 667), (355, 113)]
\$\endgroup\$
3
\$\begingroup\$

APL, 50

2↑⍎⍕(⍎x←⍞){50>|(10*⍴x)×⍺-⍵÷⍨n←⌊.5+⍺×⍵:n ⍵⋄''}¨⍳1e5

As long as you don't count eval and toString as loops

Explanation

The approach is to iterate over 1 to 10000 as denominator and calculate the numerator that most closely match the float, then check if the error is within bounds. Lastly, select the smallest pair from all the fractions found.

(⍎x←⍞) Take string input from screen, assign to x, and eval
⍳1e5 Generate array from 1 to 10000
{...}¨ For each element of the array, call function with it and (⍎x←⍞) and arguments (loop)

⍺×⍵ Multiply the arguments
⌊.5+ Round off (by adding 0.5 then rounding down)
n← Assign to n
⍺-⍵÷⍨ Divide by right argument, then subtract from left argument
(10*⍴x)× Multiply by 10 to the power of "length of x"
| Take absolute value
50> Check if less than 50 (length of x is 2 more than the no. of d.p., so use 50 here instead of 0.5)
:n ⍵⋄'' If the previous check returns true, then return the array of n and the right argument, else return empty string.

⍎⍕ toString and then eval to get an array of all the numbers in the array
2↑ Select only the first 2 elements, which is the first numerator-denominator pair found

\$\endgroup\$
2
\$\begingroup\$

GNU dc, 72 bytes

No loops - dc doesn't even have them. Instead the control comes from a single tail-recursive macro - idiomatic for dc.

?dXAr^d2*sf*sq1sd0[ld1+sd]sD[r1+r]sN[dlf*ld/1+2/dlq>Ndlq<Dlq!=m]dsmxpldp

Output:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; dc unround.dc <<< $n; done
    n = 1.7:
5
3
    n = 0.:
0
1
    n = 0.001:
1
667
    n = 3.1416:
355
113
$ 

Phew. Partial explanation in this answer.

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 111 characters

f=Module[{a=0,b=1,k},While[Round[a/b,10^-(StringLength[#]-2)]!=(k=ToExpression)@#,If[N[a/b]>k@#,b++,a++]];a/b]&

Pretty simple really, and I don't think it converges anywhere as fast as the other solutions, since the numerator and denominator only increment by one. I mostly wanted to find the simple solution to this. I'll have to see the other answers and see what clever stuff happens there.

Output

f/@{"1.7","0.0","0.001","3.1416","3.14"}
{5/3, 0, 1/667, 355/113, 22/7}

Does anyone here celebrate Pi Approximation Day?

\$\endgroup\$
  • \$\begingroup\$ No, I am only celebrating tau approximation day.=P But i just noticed that |355/113 - pi|<10^-6 =) \$\endgroup\$ – flawr Sep 25 '14 at 11:31
2
\$\begingroup\$

Applescript, >300 bytes

I wanted to do this in a language that natively does the type of rounding required. Turns out Applescript fits the bill. Then I saw the enum rounding as taught in school, and couldn't resist the using it, despite the blatant uncompetitiveness of Applescript for golfing purposes:

on u(q)
    set n to 0
    set d to 1
    set x to 0
    set AppleScript's text item delimiters to "."
    set f to 10 ^ (q's text item 2's length)
    repeat until x = q as real
        set x to (round n * f / d rounding as taught in school) / f
        if x < q then set n to n + 1
        if x > q then set d to d + 1
    end repeat
    return {n, d}
end u

log my u("1.7")
log my u("0.")
log my u("0.001")
log my u("3.1416")

This can be golfed a bit more, but probably not worth it.

Output:

(*5, 3*)
(*0, 1*)
(*1, 667*)
(*355, 113*)
\$\endgroup\$
2
\$\begingroup\$

BC, 151 148 bytes

Edit - faster and shorter version

define f(v){s=scale(x=v);for(i=r=1;i<=10^s;i+=1){t=v*i+1/2;scale=0;p=t/=1;scale=s+1;t=t/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=p;d=i}}}

same test case.

A lot is similar to the previous version, but instead of trying all possible n / d combinations, we hill-climb over the residues of v and backward quotients of multiples m==v*d and denominators d. Again the precision of the computation is the same.

Here is it untangled:

define f(v)
{
    s= scale(x=v)
    for( i=r=1; i <= 10^s; i+=1 ){
        t= v * i +1/2
        scale=0
        m=t/=1 # this rounded multiple becomes nominator if
               # backward quotient is first closest to an integer
        scale=s+1
        t= t / i +10^-s/2 # divide multiple back by denominator, start rounding again...
        scale=s
        t= t/1 - v # ...rounding done. Signed residue of backward quotient
        if( (t*= -1^(t < 0)) < r ){
            r=t
            n=m
            d=i
        }
    }
}

This version really has a mere single loop and does only $\Theta\left(\operatorname{fractional_decimals}(v)\right)$ arithmetic operations.

Original - slow version

This functions computes the smallest nominator n and denominator d such that the fraction n / d rounded to fractional_decimals(v) digits is equal to a given decimal value v.

define f(v){s=scale(v);j=0;for(i=r=1;j<=v*10^s;){scale=s+1;t=j/i+10^-s/2;scale=s;t=t/1-v;if((t*=-1^(t<0))<r){r=t;n=j;d=i};if((i+=1)>10^s){i=1;j+=1}};v}

test case:

define o(){ print "Input ",x,"\tOutput ",n,"/",d,"\n" }
f(1.7); o()
> 0
> Input 1.7       Output 5/3
> 0
f(0.); o()
> 0
> Input 0 Output 0/1
> 0
f(0.001); o()
> 0
> Input .001      Output 1/667
> 0
f(3.1416); o()
> 0
> Input 3.1416    Output 355/113
> 0

And here is it untangled:

define f(v)
{
    s=scale(x=v) # save in global for later print
    j=0
    # do a full sequential hill-climb over the residues r of v and all possible
    # fractions n / d with fractional_decimals(v) == s precision.
    for( i=r=1; j <= v * 10^s; ){
        scale=s+1
        t= j / i +10^-s/2 # start rounding...
        scale=s
        t= t/1 - v # ...rounding done. New residue, but still signed
        if( (t*= -1^(t < 0)) < r ){ # absolute residue better?
            # climb hill
            r=t
            n=j
            d=i
        }
        if( (i+=1) > 10^s ){ # next inner step. End?
            # next outer step
            i=1
            j+=1
        }
    }
    v
}

I admit, I cheated a little by emulating a second inner loop inside a single outer loop, but without using any further loop statements. And that's why it actually does $\Theta\left(v \operatorname{fractional_decimals}(v)^2\right)$ arithmetic operations.

\$\endgroup\$
  • 1
    \$\begingroup\$ you should probably move the new version to the front of the post \$\endgroup\$ – proud haskeller Sep 24 '14 at 20:05
  • \$\begingroup\$ @proudhaskeller done \$\endgroup\$ – Franki Sep 26 '14 at 21:57
1
\$\begingroup\$

C, 233

This works by calling a rationalization function r() with a starting denominator of 1. The function begins incrementing a numerator, and checking at every increment whether the resulting number, when rounded to the same number of digits as the original, has the same string representation as the original. Once the numerator has been incremented so much that the result is greater than the original, the function increments the denominator and calls itself.

This of course uses much more code, but I think the spirit of the problem exonerates this bare-bones approach; for all we know, the internal rationalize() functions of modern languages have lots of internal loops.

Note that this doesn't work for an input of "0." because that is not a standard way to write a float, so when it re-writes the float to string, the result will never be a "0.".

The specs want a function that returns values instead of just printing to screen, hence the argument-passing.

Code (ungolfed):

void r(char* x, int* a, int* b) {
    int i = -1;
    char z[32];
    double v =atof(x);
    while(1) {
        i++;
        double y = ((double)i)/((double)(*b));
        double w;
        sprintf(z, "%.*f", strlen(strchr(x,'.'))-1, y);
        if(strcmp(x, z)==0) {
            *a = i;
            return;
        }
        w = atof(z);
        if(w > v) {
            (*b)++;
            r(x, a, b);
            return;
        }
    }
}

Usage:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    int num;
    int denom = 1; // start with a denominator of 1
    r(argv[1], &num, &denom);
    printf("%d/%d\n", num, denom);
    return 0;
}

Golfed code:

typedef double D;
void r(char*x,int*a,int*b){int i=-1;char z[32];D v=atof(x);while(1){i++;D y=((D)i)/((D)(*b));D w;sprintf(z,"%.*f",strlen(strchr(x,'.'))-1,y);if(!strcmp(x,z)){*a=i;return;}w=atof(z);if(w>v){(*b)++;r(x,a,b);return;}}}
\$\endgroup\$
  • \$\begingroup\$ actually, in the Haskell library implementation (hackage.haskell.org/package/base-4.7.0.1/docs/src/…), the definition of approxRational has Just one recursive helper function, and no more looping than that. \$\endgroup\$ – proud haskeller Sep 23 '14 at 20:59
  • \$\begingroup\$ well, I was wrong, it actually has two recursive helper functions, but by the spec it is okay \$\endgroup\$ – proud haskeller Sep 23 '14 at 21:03
  • \$\begingroup\$ I wasn't trying to say that anyone's solutions were invalid, just wanted to post one without built-in rationalization :) \$\endgroup\$ – R.T. Sep 23 '14 at 21:07
  • \$\begingroup\$ of course, but the fact that the definition itself has no loops is nice, and infact, you wrote in your post "for all we know, the internal rationalize() functions of modern languages have lots of internal loops." so I checked it. \$\endgroup\$ – proud haskeller Sep 23 '14 at 21:12
  • \$\begingroup\$ anyway, how does the solution work? \$\endgroup\$ – proud haskeller Sep 23 '14 at 21:13
1
\$\begingroup\$

Pure Bash, 92 bytes

As a partial explanation for this answer, here it is ported to bash:

f=${1#*.}
q=${1//.}
for((n=0,d=1;x-q;x=2*10**${#f}*n/d+1>>1,n+=x<q,d+=x>q));{ :;}
echo $n/$d

Notably:

  • bash has integer-only arithmetic. So we appropriately scale everything up by 2*10^(number of fractional digits).
  • bash rounds down to nearest integer; the 2 in the expression above is so we can instead round to nearest integer (up or down).
  • Just one loop
  • we check if the rational overshoots or undershoots the decimal and increment the denominator or numerator accordingly.

Output:

$ for n in 1.7 0. 0.001 3.1416; do echo "    n = $n:"; ./unround.sh $n; done
    n = 1.7:
5/3
    n = 0.:
0/1
    n = 0.001:
1/667
    n = 3.1416:
355/113
$ 
\$\endgroup\$
  • \$\begingroup\$ Should be a fairly straightforward int-only port to c \$\endgroup\$ – Digital Trauma Sep 24 '14 at 23:50
1
\$\begingroup\$

JavaScript (E6) 85

F=r=>(l=>{for(n=r,d=1;l&&r!=((n=r*d+1/2|0)/d).toFixed(l);d++);})(r.length-2)||[n|0,d]

Ungolfed

F=r=>{
  l = r.length-2; // decimal digits
  if (l==0) return [r|0, 1] // if no decimal return the same (conv to number) with denominator 1

  // loop for increasing denominator 
  for(d = 2; 
      r != ( // loop until find an equal result
      // given R=N/D ==> N=R*D
      (n=r*d+1/2|0) // find possible numerator, rounding (+0.5 and trunc)
      /d).toFixed(l); // calc result to given decimals
      d++);
  return [n,d]
}

Test In FireFox/FireBug console

;["1.7","0.","0.001","3.1416","9.9999"].forEach(v => console.log(v,F(v)))

Output

1.7 [5, 3]
0. [0, 1]
0.001 [1, 667]
3.1416 [355, 113]
9.9999 [66669, 6667]
\$\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.