StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Obviously the outer floor is not redundant, since for example, <code>sqrt(2)</code> is not an integer, and thus <code>floor(sqrt(2))≠sqrt(2)</code>.</p> <p>It is also easy to see that <code>sqrt(floor(x))≠sqrt(x)</code> for non-integer <code>x</code>. Since <code>sqrt</code> is a monotone function.</p> <p>We need to find out whether or not <code>floor(sqrt(floor(x)))==floor(sqrt(x))</code> for all rationals (or reals).</p> <p>Let us prove that if <code>sqrt(n)<m</code> then <code>sqrt(n+1)<m+1</code>, for integers <code>m,n</code>. It is easy to see that</p> <pre><code>n<m^2 ⇒ n+1 < m^2+1 < m^2+2m+1 = (m+1)^2 </code></pre> <p>Therefor by the fact that <code>sqrt</code> is montone we have that</p> <pre><code>sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1 </code></pre> <p>Therefor <code>floor(sqrt(n))=floor(sqrt(n+eps))</code> for all <code>0<eps<1</code> and integer <code>n</code>. Assume otherwise that <code>floor(sqrt(n))=m</code> and <code>floor(sqrt(n+eps))=m+1</code>, and you've got a case where <code>sqrt(n)<m+1</code> however <code>sqrt(n+eps)>=m+1</code>.</p> <p>So, assuming the outer <code>floor</code> is needed, the inner <code>floor</code> is redundant.</p> <p>To put it otherwise it is always true that</p> <pre><code>floor(sqrt(n)) == floor(sqrt(floor(n))) </code></pre> <p>What about inner <code>ceil</code>?</p> <p>It is easy to see that <code>floor(sqrt(n)) ≠ floor(sqrt(ceil(n)))</code>. For example</p> <pre><code>floor(sqrt(0.001))=0, while floor(sqrt(1))=1 </code></pre> <p>However you can prove in similar way that</p> <pre><code>ceil(sqrt(n)) == ceil(sqrt(ceil(n))) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload