Un-round fractions

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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)]

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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.

Answer 9

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?

Answer 10

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*)

Answer 11

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.

Answer 12

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;}}}

Answer 13

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
$ 

Answer 14

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]