tags:

views:

711

answers:

8

I have floor(sqrt(floor(x))). Which is true:

  1. The inner floor is redundant.
  2. The outer floor is redundant.
+4  A: 

The inner floor is redundant

ichiban
there, i'll give ya the ten points lost :) I was surprised Richie got that many upvotes for an answer like that...
Peter Perháč
Anybody who downvotes me, needs to downvote Richie. I give my answer before him.
ichiban
Man, people. Leave a comment if you don't like an answer, Also, this answer is short and to the point, and correct. If you down voted this, you probably need a reality check.
GMan
+3  A: 

If x is an integer then the inner floor is redundant.

If x is not an integer then neither are redundant.

Macker
the question really is why for the second part.
kunjaan
So much bla-bla around, while Macker only got it right and concise.
majkinetor
the bla bla was trying to convince ourselves that it is true.
kunjaan
Macker is wrong.
kunjaan
Your answer was the first to be right and to the point. +1
Jose Basilio
Strange that you say it's wrong but have agreed with the same conclusions in your choice of answer. I'm confused. You didn't ask for a proof in your question btw.
Macker
I am sorry the question is still open. Could you edit it with your proof?
kunjaan
Actually, Ned Batchelder has convinced me that inner is always redundant now, well done Ned.
Macker
+5  A: 

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!

RichieHindle
I too tried out examples and feel it in my gut that the inner one is redundant but its damn hard to prove that i am correct.
kunjaan
Indeed. There was an answer saying the inner one is redundant, but before I could upvote it it got downvoted and deleted. Still, I believe that's the case.
GSerg
Can't you just say that floor(sqrt(x)) only changes value on integer values of x? If x is not an integer, then flooring it won't change the integer part of the square root.
v3
+3  A: 

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...

bbmud
+27  A: 

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)))
Elazar Leibovich
Does your solution imply that an inner ceiling would also be redundant?
kunjaan
See updated answer for the case of the ceiling.
Elazar Leibovich
I cant see any problem here. Unless somebody proves otherwise, this is correct.
kunjaan
+1 Nice to see a mathematical proof
Tom Leys
+4  A: 

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.

Ned Batchelder
+13  A: 

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.

Simon Lehmann
now that's a nice explanation. +1
Peter Perháč
There were a lot of good proofs but this one is the sweetest. Thanks.
kunjaan
Who said there's no whole integer in [sqrt(x),sqrt(x+1)]? If for example sqrt(x)==0.9 and sqrt(x+1)=1.2, then the result of floor(sqrt(floor(x))) might be different than floor(sqrt(x))
Elazar Leibovich
I'm glad you like it. After reading all the different and well done actual proofs I thought my explanation might be too informal for some tastes.
Simon Lehmann
Wow. Is there a hole in the solution?
kunjaan
@Elazar: I wrote [sqrt(x),sqrt(x)+1[ and not [sqrt(x),sqrt(x+1)[, but even then you are right (though, your example is wrong). I've corrected the interval to what I actually meant. The sqrt(x) and sqrt(x+1) of any integer x lies within the same integer interval.
Simon Lehmann
+2  A: 

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.

Demi
"floor(sqrt(n)) != floor(sqrt(m)) requires that the values of sqrt(n) and sqrt(m) differ by at least 1.0" doesn't seem to be true, if sqrt(n) = 0.999 and sqrt(m) = 1, their different by far less than 1, however floor(sqrt(n))!=floor(sqrt(m))
Elazar Leibovich
"note that n <= m < n + 1"That doesn't seem to be true, since floor(n) can be < n
melfar
good points, noted.
Demi
edited in response.
Demi