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.

\$\endgroup\$
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.

\$\endgroup\$
  • \$\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\$ – Neil Sep 18 '17 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\$ – tsh Sep 18 '17 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\$ – Neil Sep 18 '17 at 9:27
  • \$\begingroup\$ @Neil 120 -> 70 bytes. :) \$\endgroup\$ – tsh Sep 18 '17 at 9:56
  • \$\begingroup\$ Whoa, that's much better! \$\endgroup\$ – Neil Sep 18 '17 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.

\$\endgroup\$
  • \$\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\$ – Laikoni Sep 18 '17 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\$ – jferard Sep 18 '17 at 18:04
  • \$\begingroup\$ You can add the -cpp compiler flag and write f=\ in the header: Try it online! \$\endgroup\$ – Laikoni Sep 18 '17 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\$ – orlp Sep 18 '17 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\$ – jferard Sep 19 '17 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;
}
\$\endgroup\$
  • \$\begingroup\$ It also nears the probably fastest possible solution in the sense of cpu cycles, at least on conventional machines. \$\endgroup\$ – peterh Sep 24 '17 at 14:43

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.