Approximate floating point number with n-digit precision

Question

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.

Answer 1

JavaScript, O(10^p) & 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(10^p) 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.

Answer 2

Haskell, O(10^p) 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.

Answer 3

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