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.


3 Answers 3


JavaScript, O(10p) & 72 bytes


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

<math xmlns="http://www.w3.org/1998/Math/MathML">
    <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>
      <mrow><mn><output id="v1">0</output></mn></mrow>
      <mrow><mn><output id="v2">1</output></mn></mrow>
    <mn><output id="d">0</output></mn>

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

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

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

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.

  • \$\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
    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\$
    – jferard
    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\$
    – Laikoni
    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\$
    – orlp
    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\$
    – jferard
    Commented Sep 19, 2017 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;

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.