CODEWITHSUNDEEP
mathintegersquare-root
minmax
minmax

Reputation: 523

Integer ceil(sqrt(x))

The answer gives the following code for computing floor(sqrt(x)) using just integers. Is it possible to use/modify it to return ceil(sqrt(x)) instead? Alternatively, what is the preferred way to calculate such value?

Edit: Thank you all so far and I apologise, I should have make it more explicit: I was hoping there is more "natural" way of doing this that using floor(sqrt(x)), possibly plus one. The floor version uses Newton's method to approach the root from above, I thought that maybe approaching it from below or similar would do the trick.

For example the answer even provides how to round to nearest integer: just input 4*x to the algorithm.

Upvotes: 6

Views: 4368

Answers (2)

Rory Daulton
Rory Daulton

Reputation: 22564

If x is an exact square, the ceiling and the floor of the square root are equal; otherwise, the ceiling is one more than the square root. So you could use (in Python),

result = floorsqrt(x)
if result * result != x:
    result += 1

Modifying the code you linked to is not a good idea, since that code uses some properties of the Newton-Raphson method of calculating the square root. Much theory has been developed about that method, and the code uses that theory. The code I show is not as neat as modifying your linked code but it is safer and probably quicker than making a change in the code.

Upvotes: 7

OmG
OmG

Reputation: 18838

You can use this fact that:

floor(x) = (ceil(x) - 1) if x \not \in Z else ceil(x)

Hence, check if N is in the form 2^k, the code is the same, and if it is not, you can -1 the result of the current code.

Upvotes: 0

Related Questions