Fifnmar edited 4 年，10 月前
今天早上一个同学跟我探讨了一个有趣的问题：
「只用整数，用二分法求出一个整数的平方根，如果结果不是整数则向上取整。」
因为想要的是 $\lceil \sqrt{n} \rceil$，所以二分的时候要考虑明白退出条件。
所求得的根 $m$ 应该满足这个要求：
$$
(m - 1)^2 < n \le m^2
$$
但实际写代码的时候请注意到乘法可能溢出，所以改写成这个样子：
$$
\begin {cases}
m - 1 < \frac{n}{m-1} \
m \ge \frac{n}{m}
\end {cases}
$$
可是整数除法还默认向下取整，这怎么办。我思考了一下，决定引入余数。
$$
\begin{cases}
m - 1 < \frac{n}{m - 1},&n \mod m - 1 = 0 \
m - 1 \le \frac{n}{m - 1},&n \mod m - 1 \ne 0 \
m \ge \frac{n}{m},&n \mod m = 0 \
m > \frac{n}{m},&n \mod m \ne 0
\end{cases}
$$
代码：
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <limits>
#include <random>
uint32_t ceil_sqrt(uint32_t const num) {
if (num <= 2) {
return num; // Defend from corner cases.
}
uint32_t lo = 0, hi = num; // range [lo, hi).
uint32_t mid;
while (true) {
mid = lo + (hi - lo) / 2;
if (mid < (num / mid) + (num % mid != 0)) {
lo = mid + 1;
} else if ((mid - 1) > num / (mid - 1) - (num % (mid - 1) == 0)) {
hi = mid;
} else {
break;
}
}
return mid;
}
void test_floor_sqrt() {
assert(ceil_sqrt(0) == 0);
assert(ceil_sqrt(1) == 1);
assert(ceil_sqrt(2) == 2);
assert(ceil_sqrt(4) == 2);
assert(ceil_sqrt(5) == 3);
std::default_random_engine e(std::chrono::system_clock::now().time_since_epoch().count());
std::uniform_int_distribution<uint32_t> u(std::numeric_limits<uint32_t>::min(),
std::numeric_limits<uint32_t>::max());
// random test;
for (uint32_t i = 0; i < 123456; ++i) {
auto temp = u(e);
assert(ceil_sqrt(temp) == std::ceil(std::sqrt(temp)));
}
}
int main() {
using namespace std;
test_floor_sqrt();
}
从这个例子可以看出，其实我只是把原始的式子应用了一下整数向上取整的方法：如果有余就加一。
不知道有没有更好的方法呢？
经过学习，我发现这篇文章的思路复杂了。想要上取整，可以这样做：
$$
\lceil x / y \rceil = \lfloor (x + y - 1) / y \rfloor
$$