Approximate floating point number with n-digit precision
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.