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) &amp; 72 bytes

r=&gt;p=&gt;{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b&lt;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=&gt;p=&gt;{for(a=0,b=1,t=10**p;(a/b*t|0)-(r*t|0);a/b&lt;r?a++:b++);return[a,b]}
&lt;math xmlns="http://www.w3.org/1998/Math/MathML"&gt;
  &lt;mrow&gt;
    &lt;mn&gt;0.&lt;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" /&gt;&lt;/mn&gt;
    &lt;mo&gt;=&lt;/mo&gt;
    &lt;mfrac&gt;
      &lt;mrow&gt;&lt;mn&gt;&lt;output id="v1"&gt;0&lt;/output&gt;&lt;/mn&gt;&lt;/mrow&gt;
      &lt;mrow&gt;&lt;mn&gt;&lt;output id="v2"&gt;1&lt;/output&gt;&lt;/mn&gt;&lt;/mrow&gt;
    &lt;/mfrac&gt;
    &lt;mo&gt;=&lt;/mo&gt;
    &lt;mn&gt;&lt;output id="d"&gt;0&lt;/output&gt;&lt;/mn&gt;
  &lt;/mrow&gt;
&lt;/math&gt;




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