Alex Rivera | Logout

Which floor is redundant in floor(sqrt(floor(x)))?

Asked 2009-05-17T20:06:57.923
14

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

  1. The inner floor is redundant.
  2. The outer floor is redundant.
Edit
Report

2 Answers

4

The inner floor is redundant

answered 2009-05-17T20:09:29.057
2

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.

answered 2009-05-17T20:53:54.160

Your Answer