# Approximate floating point number with n-digit precision

We have a floating point number r between 0 and 1, and an integer p.

Find the fraction of integers with the smallest denominator, which approximates r with at least p-digit precision.

• Inputs: r (a floating point number) and p (integer).
• Outputs: a and b integers, where
• a/b (as float) approximates r until p digits.
• b is the possible smallest such positive integer.

For example:

• if r=0.14159265358979 and p=9,
• then the result is a=4687 and b=33102,
• because 4687/33102=0.1415926530119026.

Any solution has to work in theory with arbitrary-precision types, but limitations caused by implementations' fixed-precision types do not matter.

Precision means the number of digits after "0." in r. Thus, if r=0.0123 and p=3, then a/b should start with 0.012. If the first p digits of the fractional part of r are 0, undefined behavior is acceptable.

Win criteria:

• The algorithmically fastest algorithm wins. Speed is measured in O(p).
• If there are multiple fastest algorithms, then the shortest wins.
• My own answer is excluded from the set of the possible winners.

P.s. the math part is actually much easier as it seems, I suggest to read this post.

# JavaScript, O(10p) & 72 bytes

r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}


It is trivial to prove that the loop will be done after at most O(10p) iterations.

f=
r=>p=>{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b<r?a++:b++);return[a,b]}
<math xmlns="http://www.w3.org/1998/Math/MathML">
<mrow>
<mn>0.<input type="text" id="n" value="" oninput="[p,q]=f(+('0.'+n.value))(n.value.length);v1.value=p;v2.value=q;d.value=p/q" /></mn>
<mo>=</mo>
<mfrac>
<mrow><mn><output id="v1">0</output></mn></mrow>
<mrow><mn><output id="v2">1</output></mn></mrow>
</mfrac>
<mo>=</mo>
<mn><output id="d">0</output></mn>
</mrow>
[/itex]

Many thanks to Neil's idea, save 50 bytes.

• Why are you fiddling around with padEnd and match? Can't you just slice each string to the correct length and then subtract them?
– Neil
Sep 18 '17 at 9:14
• @Neil Sorry I hadn't catch your point. The added padEnd is used for testcase f(0.001,2) and f(0.3,2).
– tsh
Sep 18 '17 at 9:23
• I was thinking you could simplify down to something along the lines of (r,p)=>{for(a=0,b=1;${a/b}.slice(0,p+2)-${r}.slice(0,p+2);a/b<r?a++:b++);return[a,b]} (not fully golfed).
– Neil
Sep 18 '17 at 9:27
• @Neil 120 -> 70 bytes. :)
– tsh
Sep 18 '17 at 9:56
• Whoa, that's much better!
– Neil
Sep 18 '17 at 9:58

# Haskell, O(10p) in worst case 121 119 bytes

g(0,1,1,1)
g(a,b,c,d)r p|z<-floor.(*10^p),u<-a+c,v<-b+d=last$g(last$(u,v,c,d):[(a,b,u,v)|r<u/v])r p:[(u,v)|z r==z(u/v)]


Try it online!

Saved 2 bytes thanks to Laikoni

At each step, the new interval is one half of the previous interval. Thus, the interval size is 2**-n, where n is the current step. When 2**-n < 10**-p, we are sure to have the right approximation. Yet if n > 4*p then 2**-n < 2**-(4*p) == 16**-p < 10**-p. The conclusion is that the algorithm is O(p).

EDIT As pointed out by orlp in a comment, the claim above is false. In the worst case, r = 1/10**p (r= 1-1/10**p is similar), there will be 10**p steps : 1/2, 1/3, 1/4, .... There is a better solution, but I don't have the time right now to fix this.

• I know code golf is only the secondary goal, but you can drop the f= and save two bytes with z<-floor.(*10^p),u<-a+c,v<-b+d. Sep 18 '17 at 17:53
• @Laikoni I did not count the two bytes. I don't know how to remove f= on TIO in Haskell code. Sep 18 '17 at 18:04
• You can add the -cpp compiler flag and write f=\  in the header: Try it online! Sep 18 '17 at 18:10
• "At each step, the new interval is one half of the previous interval." How do you know this? The first step is 1/2, yes, but then the next step is for example the mediant of 1/2 and 1/1 giving 2/3, which is not halving the interval.
– orlp
Sep 18 '17 at 21:05
• @orlp You're absolutelty right. I was far too optimistic and the complexity is O(10^p) in the worst case. I have a better solution but don't have the time to write it right now. Sep 19 '17 at 18:34

### C, 473 bytes (without context), O(p), non-competing

This solution uses the math part detailed in this excellent post. I calculated only calc() into the answer size.

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

void calc(float r, int p, int *A, int *B) {
int a=0, b=1, c=1, d=1, e, f;
int tmp = r*pow(10, p);
float ivl = (float)(tmp) / pow(10, p);
float ivh = (float)(tmp + 1) / pow(10, p);

for (;;) {
e = a + c;
f = b + d;

if ((ivl <= (float)e/f) && ((float)e/f <= ivh)) {
*A = e;
*B = f;
return;
}

if ((float)e/f < ivl) {
a = e;
b = f;
continue;
} else {
c = e;
d = f;
continue;
}
}
}

int main(int argc, char **argv) {
float r = atof(argv[1]);
int p = atoi(argv[2]), a, b;
calc(r, p, &a, &b);
printf ("a=%i b=%i\n", a, b);
return 0;
}

• It also nears the probably fastest possible solution in the sense of cpu cycles, at least on conventional machines. Sep 24 '17 at 14:43