9
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
7
\$\begingroup\$

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> </math>

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

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Why are you fiddling around with padEnd and match? Can't you just slice each string to the correct length and then subtract them? \$\endgroup\$ Commented Sep 18, 2017 at 9:14
  • \$\begingroup\$ @Neil Sorry I hadn't catch your point. The added padEnd is used for testcase f(0.001,2) and f(0.3,2). \$\endgroup\$ Commented Sep 18, 2017 at 9:23
  • \$\begingroup\$ 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). \$\endgroup\$ Commented Sep 18, 2017 at 9:27
  • \$\begingroup\$ @Neil 120 -> 70 bytes. :) \$\endgroup\$ Commented Sep 18, 2017 at 9:56
  • \$\begingroup\$ Whoa, that's much better! \$\endgroup\$ Commented Sep 18, 2017 at 9:58
4
\$\begingroup\$

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

I used the algorithm from https://math.stackexchange.com/questions/2432123/how-to-find-the-fraction-of-integers-with-the-smallest-denominator-matching-an-i.

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.

Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 18, 2017 at 17:53
  • \$\begingroup\$ @Laikoni I did not count the two bytes. I don't know how to remove f= on TIO in Haskell code. \$\endgroup\$ Commented Sep 18, 2017 at 18:04
  • \$\begingroup\$ You can add the -cpp compiler flag and write f=\ in the header: Try it online! \$\endgroup\$ Commented Sep 18, 2017 at 18:10
  • \$\begingroup\$ "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. \$\endgroup\$ Commented Sep 18, 2017 at 21:05
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Sep 19, 2017 at 18:34
0
\$\begingroup\$

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; }
Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ It also nears the probably fastest possible solution in the sense of cpu cycles, at least on conventional machines. \$\endgroup\$ Commented Sep 24, 2017 at 14:43

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.