I have floor(sqrt(floor(x)))
. Which is true:
- The inner
floor
is redundant. - The outer
floor
is redundant.
I have floor(sqrt(floor(x)))
. Which is true:
floor
is redundant.floor
is redundant.If x is an integer then the inner floor is redundant.
If x is not an integer then neither are redundant.
Intuitively I believe the inner one is redundant, but I can't prove it.
You're not allowed to vote me down unless you can provide a value of x that proves me wrong. 8-)
Edit: See v3's comment on this answer for proof - thanks, v3!
The outer floor is not redundant. Counterexample: x = 2.
floor(sqrt(floor(2))) = floor(sqrt(2)) = floor(1.41...)
Without the outer floor the result would be 1.41...
Obviously the outer floor is not redundant, since for example, sqrt(2)
is not an integer, and thus floor(sqrt(2))!=sqrt(2)
.
It is also easy to see that sqrt(floor(x))!=sqrt(x)
for non-integer x
. Since sqrt
is a monotone function.
We need to find out whether or not floor(sqrt(floor(x)))==floor(sqrt(x))
for all rationals (or reals).
Let us prove that if sqrt(n)<m
then sqrt(n+1)<m+1
, for integers m,n
. It is easy to see that
n<m^2 -> n+1 < m^2+1 < m^2+2m+1 = (m+1)^2
Therefor by the fact that sqrt
is montone we have that
sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1
Therefor floor(sqrt(n))=floor(sqrt(n+eps))
for all 0<eps<1
and integer n
. Assume otherwise that floor(sqrt(n))=m
and floor(sqrt(n+eps))=m+1
, and you've got a case where sqrt(n)<m+1
however sqrt(n+eps)>=m+1
.
So, assuming the outer floor
is needed, the inner floor
is redundant.
To put it otherwise it is always true that
floor(sqrt(n)) == floor(sqrt(floor(n)))
What about inner ceil
?
It is easy to see that floor(sqrt(n)) != floor(sqrt(ceil(n)))
. For example
floor(sqrt(0.001))=0, while floor(sqrt(1))=1
However you can prove in similar way that
ceil(sqrt(n)) == ceil(sqrt(ceil(n)))
The inner floor is redundant. A proof by contradiction:
Assume the inner floor is not redundant. That would mean that:
floor(sqrt(x)) != floor(sqrt(x+d))
for some x and d where floor(x) = floor(x+d). Then we have three numbers to consider: a = sqrt(x), b = floor(sqrt(x+d)), c = sqrt(x+d). b is an integer, and a < b < c. That means that a^2 < b^2 < c^2, or x < b^2 < x+d. But if b is an integer, then b^2 is an integer. Therefore floor(x) < b^2, and b^2 <= floor(x+d), and then floor(x) < floor(x+d). But we started by assuming floor(x) = floor(x+d). We've reached a contradiction, so our assumption is false, and the inner floor is redundant.
The inner one is redundant, the outer one of course not.
The outer one is not redundant, because the square root of a number x only results in an integer if x is a square number.
The inner one is redundant, because the square root for any number in the interval [x,x+1[ (where x is an integer) always lies within the interval [floor(sqrt(x)),ceil(sqrt(x))[ and therefore you don't need to floor a number before taking the square root of it, if you are only interested the integer part of the result.
If the inner floor were not redundant, then we would expect that floor(sqrt(n)) != floor(sqrt(m)), where m = floor(n)
note that n - 1 < m <= n. m is always less than or equal to n
floor(sqrt(n)) != floor(sqrt(m)) requires that the values of sqrt(n) and sqrt(m) differ by at least 1.0
however, there are no values n for which the sqrt(n) differs by at least 1.0 from sqrt(n + 1), since for all values between 0 and 1 the sqrt of that value is < 1 by definition.
thus, for all values n, the floor(sqrt(n)) == floor(sqrt(n + 1)). This is in contradiction to the original assumption.
Thus the inner floor is redundant.