Is it possible to find closest number to a given irrational one, which is obtained by dividing 2 numbers in a given range faster than O(n^2)? - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-26T17:43:08Z https://cstheory.stackexchange.com/feeds/question/50971 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/50971 -2 Is it possible to find closest number to a given irrational one, which is obtained by dividing 2 numbers in a given range faster than O(n^2)? Omegon https://cstheory.stackexchange.com/users/65541 2022-01-13T00:03:42Z 2022-01-13T00:03:42Z <p>Let's say I have a range from 11 to 99 I need to find:</p> <pre><code>abs(a/b)-k = min, a nd b - integer, k-an irrational number </code></pre> <p>I can just look at all pairs of numbers in quadratic time</p> <pre><code>for(i=11;i&lt;99;++i) for(j=i;j&lt;99;++j) abs()... </code></pre> <p>and find the minimum, but is it possible to do this in linear time, for example?</p>