求整数的平方根向上取整

Question

答案提供了以下代码来计算floor(sqrt(x))，能否使用/修改它来返回ceil(sqrt(x))呢？或者，有什么更好的方法来计算这样的值吗？

编辑：非常感谢大家，我应该更明确一些：我希望有更“自然”的方法来完成这个任务，而不是使用floor(sqrt(x))，可能再加上一个。 floor版本使用牛顿法从上方接近根，我认为从下方或类似的方法接近可能会奏效。

例如，答案甚至提供了如何四舍五入到最近整数的方法：只需将4*x输入算法即可。

- minmax

Answer 1

如果x是一个完全平方数，那么其平方根的上取整和下取整相等；否则，上取整比平方根多1。你可以在Python中使用以下代码：

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

修改你提供的代码并不是一个好主意，因为那段代码使用了牛顿迭代法计算平方根的一些属性。这种方法已经有了很多理论的发展，并且代码也使用了这个理论。我展示的代码虽然不如修改你链接的代码整洁，但比起对代码进行更改，它更加安全和可能更快。

- Rory Daulton

Answer 2

你可以利用这个事实：

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

因此，检查N是否为2^k形式，代码相同，如果不是，则可以将当前代码的结果-1。

- OmG