禁止使用sqrt等返回浮点数的函数，如何最高效的得到最小的不小于给定正整数的完全平方数？

好的，咱们不依赖那些花里胡哨的浮点数函数，直接用最实在的整数运算，来找一个大于等于给定正整数的最小的完全平方数。这事儿说起来有点意思，虽然听起来简单，但里面的门道可以好好说道说道。

咱们的目标是找到一个数 `N`，使得 `N` 是一个完全平方数（也就是 `N = k k`，其中 `k` 是一个整数），并且 `N` 是所有满足大于等于给定正整数 `x` 的完全平方数中最小的那个。

举个例子，如果给定的正整数是 `10`。我们知道完全平方数有 `1, 4, 9, 16, 25, ...`。其中大于等于 `10` 的完全平方数有 `16, 25, 36, ...`。最小的那个就是 `16`。

最直接但效率不高的想法（先有个概念）：

最直观的想法可能是这样：从 `1` 开始，一个个平方，看看什么时候平方出来的数第一次大于或等于我们的目标数 `x`。

比如 `x = 10`：
`1 1 = 1` (小于 10)
`2 2 = 4` (小于 10)
`3 3 = 9` (小于 10)
`4 4 = 16` (大于等于 10了！找到了，就是16。)

这个方法能得到正确答案，但效率上，如果 `x` 特别大，比如是个几百万的数，我们就要平方好几十万次才能找到。这就不太“高效”了。

核心思路：找“根”的整数部分

咱们知道，如果一个数 `N` 是完全平方数，那么它的平方根 `sqrt(N)` 是一个整数。反过来，如果一个数的平方根是整数，那么它就是完全平方数。

我们想找的数 `N` 是一个完全平方数，并且 `N >= x`。
假设我们找到了那个整数 `k`，使得 `N = k k`。
那么，我们有 `k k >= x`。

如果我们能找到一个整数 `k`，使得 `k` 是所有满足 `k k >= x` 的整数中最小的一个，那问题就迎刃而解了。

怎么样才能找到这个最小的 `k` 呢？
如果 `x` 本身就是一个完全平方数（比如 `x=9`），那么 `k` 就是它的平方根（`k=3`）。
如果 `x` 不是一个完全平方数（比如 `x=10`），那么它的平方根会是一个小数（`sqrt(10) ≈ 3.16`）。我们需要的 `k` 必须是大于这个小数的最小整数，也就是 `4`。

这不就和我们之前说的“找到小于等于 `x` 的最大平方根，然后加一”是一个意思吗？
关键在于，我们不能用 `sqrt`。

利用整数二分查找来找“根”

既然不能直接算平方根，我们能不能用一种“猜测”和“逼近”的方法来找到这个整数 `k` 呢？ 整数二分查找（Binary Search）就是干这个的！

二分查找的核心思想是：在一个有序的范围内，不断将搜索范围缩小一半，直到找到目标。

我们现在需要找的 `k`，它一定在一个范围内。
下限： 最小的可能 `k` 是 `1`（因为 `x` 是正整数，所以平方根至少是 `1`）。
上限： 如果 `x` 很大，比如 `10^12`，那么它的平方根大概是 `10^6`。如果 `x` 是 `10^18`，平方根大概是 `10^9`。一般来说，`k` 不会比 `x` 大多少，甚至比 `x` 小很多。一个比较保险的上限可以是 `x` 本身，或者为了更保险一些，我们可以设一个更大的值，比如 `x + 1` 或者 `2 10^9`（如果考虑到 64 位整数的上限）。但为了高效，我们应该选择一个相对紧凑但绝对安全的范围。考虑 `kk >= x`，如果 `k = x`，那么 `kk = xx`，这远大于 `x`（除非 `x=1`）。所以，`x` 本身绝对是个安全的上限。更具体地说，如果 `kk = x`，那么 `k <= x`。如果 `kk > x`，那么 `k` 的值可能比 `x` 的平方根大一点点，但通常不会超过 `x` 本身太多。一个更紧凑的上限可以是 `x / 2 + 1` (对于 `x > 1`)，因为 `(x/2+1)^2 = x^2/4 + x + 1`，当 `x` 很大时，这远大于 `x`。不过，最简单安全的上限就是 `x` 本身。为了通用性，我们可以考虑一个稍微宽松但一定包含答案的范围，比如 `[0, x]` 或者 `[0, x+1]`。

我们用一个范围 `[low, high]` 来表示 `k` 可能的取值范围。
初始时，`low = 0` (或者 `1`，因为 `x` 是正整数，平方根不可能是 `0`)，`high = x`。

二分查找的过程：

1. 设定初始范围：`low = 0`, `high = x`.
2. 当 `low <= high` 时，重复以下步骤：
计算中间值：`mid = low + (high low) / 2` （这样可以避免 `low + high` 溢出）。
计算 `mid_squared = mid mid`。
关键的判断：
如果 `mid_squared == x`：恭喜你，`x` 本身就是完全平方数，并且 `mid` 就是它的平方根。我们找到的最小的、大于等于 `x` 的完全平方数就是 `x`。可以直接返回 `x`（或者 `mid mid`）。
如果 `mid_squared < x`：这意味着 `mid` 太小了，它的平方还没达到 `x`。我们需要更大的 `k`。所以，我们应该在 `[mid + 1, high]` 这个范围内继续查找。将 `low` 更新为 `mid + 1`。
如果 `mid_squared > x`：这意味着 `mid` 太大了，它的平方已经超过了 `x`。但是，这个 `mid` 是一个潜在的答案（因为它对应的平方 `mid mid` 大于等于 `x`）。我们想要的是满足 `kk >= x` 的最小的 `k`。所以，`mid` 可能是我们正在寻找的那个“最小的根”，但可能还有更小的 `k`（比如 `mid1`）也满足条件。因此，我们应该尝试在 `[low, mid 1]` 这个范围里寻找更小的可能性，同时记住 `mid` 是一个“候选答案”。这里我们可以用一个变量来记录“当前找到的满足 `kk >= x` 的最小 `k`”。我们暂时不用管它，而是缩小范围，让 `high = mid 1`。

对结果的处理：

上面的二分查找过程，我们是在找那个“最小的整数 `k`，使得 `kk >= x`”。当循环结束时（即 `low > high`），这个 `low` 就是我们寻找的那个最小的整数 `k`。

举个例子，`x = 10`：
初始：`low = 0`, `high = 10`. `ans = 0` (用来记录可能的最小根)
第一次：`mid = 0 + (10 0) / 2 = 5`. `mid_squared = 5 5 = 25`. `25 > 10`.
`mid` 的平方大于 `x`，说明 `mid=5` 是一个可能的根，但可能不是最小的。记录 `ans = 5`。
缩小范围到 `[low, mid 1]`，即 `high = 5 1 = 4`.
第二次：`low = 0`, `high = 4`. `mid = 0 + (4 0) / 2 = 2`. `mid_squared = 2 2 = 4`. `4 < 10`.
`mid` 的平方小于 `x`，说明 `mid=2` 太小了。我们需要更大的根。
缩小范围到 `[mid + 1, high]`，即 `low = 2 + 1 = 3`.
第三次：`low = 3`, `high = 4`. `mid = 3 + (4 3) / 2 = 3`. `mid_squared = 3 3 = 9`. `9 < 10`.
`mid` 的平方小于 `x`，说明 `mid=3` 太小了。
缩小范围到 `[mid + 1, high]`，即 `low = 3 + 1 = 4`.
第四次：`low = 4`, `high = 4`. `mid = 4 + (4 4) / 2 = 4`. `mid_squared = 4 4 = 16`. `16 > 10`.
`mid` 的平方大于 `x`，说明 `mid=4` 是一个可能的根，并且比之前的 `ans=5` 小。记录 `ans = 4`.
缩小范围到 `[low, mid 1]`，即 `high = 4 1 = 3`.
第五次：`low = 4`, `high = 3`. `low > high`，循环结束。

循环结束后，我们记录的“最小的、平方大于等于 `x` 的那个数的“根””（也就是我们上面用 `ans` 记录的）是 `4`。
所以，最终的结果就是 `ans ans`，即 `4 4 = 16`。

更简洁的二分查找实现方式：

上面的方法需要一个额外的变量来记录“可能的最小根”。其实我们可以稍微调整一下二分查找的逻辑，让它直接找到那个最小的整数 `k`。

我们搜索的范围是 `[0, x]` （或者更优化的 `[0, x/2 + 1]`，或者 `[0, 210^9]`，取决于 `x` 的最大值）。
我们的目标是找到第一个 `mid`，使得 `mid mid >= x`。

```cpp
long long find_smallest_square(int x) {
if (x <= 0) return 0; // 或者抛出错误，根据需求定义
if (x == 1) return 1; // 特殊情况

long long low = 0;
// 确定的上限，确保包含所有可能的根。
// 如果x非常大，x/2+1仍然可能不够，但对于int类型的x，
// 它的平方根不会超过大约65536。
// 为了通用性，并且避免浮点数，可以使用一个足够大的常数作为上限
// 或者根据x的类型动态计算一个安全的上限。
// 对于int x，其平方根的上限大约是sqrt(INT_MAX) ≈ 46340。
// 我们可以将high设为 x/2 + 1，或者更稳妥一些的 x+1，甚至是一个固定的较大值。
// 这里使用x+1作为安全的上限，因为即使x=1，平方根也是1，x+1=2。
// 如果x很大，比如INT_MAX，那么其平方根的上限远小于x。
// 一个更精确的上界是 ceil(sqrt(x))。
// 但为了不用sqrt，我们可以考虑 x 本身作为上限，
// 或者 x / 2 + 1 是一个不错的选择，因为它能覆盖大部分情况。
// 还有一个更紧凑但仍安全的上限是：如果 x > 1, 那么 x 的平方根k 满足 kk >= x。
// 如果k > x/2, 那么 kk > xx/4。当 x 足够大时，xx/4 > x。
// 所以 x/2 + 1 是一个不错的上限。
// 让我们用一个稍微更保守但保证正确的上限：如果 x=1，high=1。如果x>1，high=x。
// 实际上，对于int x，它的平方根不会超过 65536 (2^16)，所以一个硬编码的上限如 65536
// 对于大多数情况都是足够的，但如果x是long long，就需要更大的上限。
// 我们就用 x+1 作为通用上限吧，它是安全的。
long long high = x + 1;

long long ans_root = 0; // 用于存储找到的最小的根

while (low <= high) {
long long mid = low + (high low) / 2;
// 避免 mid mid 溢出
if (mid > 0 && mid > 2000000000LL / mid) { // 如果 mid 很大，midmid 可能溢出
// 如果 mid 已经大到 midmid 会溢出（对于64位整数，大概在 310^9 左右的平方）
// 那么mid的平方肯定大于任何 int x 的值。
// 我们需要的是小于等于mid的根，所以将范围缩小到左边。
high = mid 1;
continue;
}
long long mid_squared = mid mid;

if (mid_squared >= x) {
// mid 可能是我们要找的最小的根，记录下来，并尝试在左边找更小的
ans_root = mid; // mid 是一个可能的答案
high = mid 1;
} else {
// mid 太小了，需要在右边找
low = mid + 1;
}
}
// 循环结束后，ans_root 就是小于等于x的最大的整数，其平方小于x。
// 不对，ans_root 记录的是 mid_squared >= x 的那个 mid。
// 所以 ans_root 就是满足条件的最小的那个整数。
return ans_root ans_root;
}
```

更精炼的二分查找逻辑（直接找到目标 `k`）：

上面的代码还可以再精简一下。我们寻找的是最小的 `k` 使得 `kk >= x`。

```cpp
long long find_smallest_square_refined(int x) {
if (x <= 0) return 0; // 假设输入是正整数
if (x == 1) return 1;

long long low = 1; // 最小的根可能是1
// 找到一个足够大的上限，确保搜索空间包含正确的根。
// 对于 int x，平方根的上限大约是 46341。
// 为了避免溢出，我们可以设一个比 x/2 + 1 更稳妥的上限，比如 65536。
// 如果x本身就很大，比如接近INT_MAX，那么它的平方根不会超过 46340。
// 所以，46341 是一个相当安全的上限，可以覆盖所有int的平方根。
// 如果 x 可以是 long long，则需要动态计算上限。
// 我们这里假设 x 是 int。
long long high = 46341; // 或者 x，更通用但可能不那么快
// 为了更符合二分查找的泛用性，我们先用 x+1 作为上限
// high = x + 1;

long long result_root = 0; // 存储找到的最小的根

while (low <= high) {
long long mid = low + (high low) / 2;

// 再次检查溢出问题：mid mid
// 确保 mid 不会过大，导致 mid mid 溢出 long long
// 3 10^9 的平方已经超过 long long 最大值
// 如果 mid 超过约 3,037,000,499，那么 midmid 会溢出
// 对于 int x，我们最大需要考虑的 mid 大约是 46340。
// 46340 46340 约等于 2.1 10^9，在 long long 范围内是安全的。
// 所以，上面的 46341 作为 high 是没问题的。

long long mid_squared = mid mid;

if (mid_squared >= x) {
// mid 是一个可能的答案，记录它，然后尝试在左边找更小的
result_root = mid;
high = mid 1;
} else {
// mid 太小了，需要在右边找
low = mid + 1;
}
}
// 当循环结束时，result_root 就是满足 midmid >= x 的最小的那个 mid
return result_root result_root;
}
```

为什么 `high = 46341` 对 `int x` 是安全的？

`int` 在 C++ 中通常是 32 位有符号整数，最大值为 `2^31 1` (约 `2.1 10^9`)。
我们需要找到 `k` 使得 `kk >= x`。
最大的 `x` 是 `2^31 1`。
它的平方根大概是 `sqrt(2.1 10^9) ≈ 46340.95`。
所以，我们需要的 `k` 最大不会超过 `46341`。
如果我们设置 `high = 46341`，那么 `mid` 的最大值也不会超过 `46341`。
`46341 46341` 的结果约为 `2.147 10^9`，这个值虽然接近 `INT_MAX`，但仍在 `long long` 的安全范围内（`long long` 最大约 `9 10^18`）。
所以，使用 `high = 46341` 是一个非常高效且安全的上限。

总结一下最高效的方案：

1. 确定搜索范围： 我们要找的整数 `k` 满足 `kk >= x`。下限可以设为 `1`。上限对于 `int x` 可以安全地设为 `46341`。
2. 整数二分查找：
设置 `low = 1`, `high = 46341` (或者更通用但可能稍慢的 `x+1`)。
设置一个变量 `ans_root = 0` 来记录当前找到的满足 `midmid >= x` 的最小的 `mid`。
在 `while (low <= high)` 循环中：
计算 `mid = low + (high low) / 2`。
计算 `mid_squared = mid mid`。
如果 `mid_squared >= x`：说明 `mid` 是一个潜在的答案，我们将 `ans_root` 更新为 `mid`，并尝试在更小的范围内寻找，所以 `high = mid 1`。
如果 `mid_squared < x`：说明 `mid` 太小了，我们需要在更大的范围内寻找，所以 `low = mid + 1`。
3. 返回结果： 循环结束后，`ans_root` 中存储的就是满足条件的最小整数 `k`。最终结果就是 `ans_root ans_root`。

举例（再次确认）： `x = 10`

`low = 1`, `high = 46341`. `ans_root = 0`.
`mid = 1 + (46341 1) / 2 = 23171`. `midmid` 远大于10. `ans_root = 23171`, `high = 23170`.
... (继续二分) ...
假设当前是 `low = 1`, `high = 5`. `ans_root = 5` (之前某个mid算出来大于10).
`mid = 1 + (5 1) / 2 = 3`. `midmid = 9`. `9 < 10`. `low = 3 + 1 = 4`.
`low = 4`, `high = 5`. `ans_root = 5`.
`mid = 4 + (5 4) / 2 = 4`. `midmid = 16`. `16 >= 10`. `ans_root = 4`. `high = 4 1 = 3`.
`low = 4`, `high = 3`. `low > high`. 循环结束.
返回 `ans_root ans_root = 4 4 = 16`.

这个方法非常高效，因为它每次将搜索范围缩小一半，时间复杂度是对数级的 O(log N)，其中 N 是上限（比如 46341）。这比线性扫描要快太多了。

关于“去除让这篇文章看起来是AI撰写的痕迹”

这部分需要点技巧。AI 的语言风格往往是：
过于标准和正式。
缺乏个人色彩和口语化的表达。
结构化非常强，段落清晰，但有时显得生硬。
喜欢用“此外”、“然而”、“因此”等连接词。
对于概念的解释，有时会用非常严谨但略显枯燥的定义。

为了避免这些，我尝试做了以下几点：

使用更自然的语言： 像“咱们”、“这事儿”、“花里胡哨”、“门道”、“干这个的”等词汇，尽量模仿日常交流的风格。
适当的省略和强调： 有时会把话说得稍微不那么“完整”，但意思能明白，比如直接说“找‘根’的整数部分”。
举例说明： 在解释概念时，引入具体数字例子，并详细说明过程，让解释更生动。
讨论方法的优缺点： 分析方法的效率，并说明为什么某个方法“不那么高效”。
语气上的转变： 在讲解过程中，语气会从介绍问题到分析方法，再到总结结论，有一个自然的过渡。
避免过于直白的“提示”： AI 可能会说“请注意这里”，我则会用“关键的判断”或直接将逻辑呈现在代码或描述中。
对上限的讨论： 在选择 `high` 这个上限时，不是简单地给出一个数字，而是讨论了为什么是这个数字，以及这个数字的安全性，这更像是一个经验性的总结。

当然，完全去除 AI 的痕迹是个持续的挑战，因为 AI 本身就在不断学习和模拟人类的表达方式。我的目标是让这篇解答听起来更像是有人在用心为你讲解一个技术问题，而不是一个冷冰冰的机器回答。

希望这些解释和方法能够帮助你！

为了方便讨论，我们假设输入值为i，输出值为result^2。同时我们不妨默认i是一个大于等于1的整数，忽略corner case们。

题目的要求就是找到一个result，使得(result-1)^2 < i <= result^2。同时根据题目的要求，我们在整个计算过程中不引入任何浮点数（否则我可以手写一个等价于sqrt的浮点数函数）。

这道题目的naive解是O(N^0.5)的，从1开始一个一个试，每试一次的代价是固定的，试到ceil(sqrt(i))，也就是其平方根的上取整的时候，就搞定了，一共需要试N^0.5次

       uint32_t naive(uint32_t i) {     for (uint32_t result = 1; result <= i; result ++) {         if ((result - 1) * (result - 1) < i &&                  i <= result * result) {             return result * result;         }     } }     

如果你在面试的时候遇到这道题，那上面的方法就显得太low了。这道题面试的正解是binary search。我们知道需要的result一定在1和i之间，因此通过二分法测试，我们可以把测试的次数减小到O(log N)

       uint32_t bin_search(uint32_t i) {     uint32_t head   = 1;     uint32_t tail   = i;     uint32_t result = 0;          if (tail >= (1 << 16)) {         // 这里记得检查一下overflow         tail = (1 << 16) - 1;     }      result = (head + tail) / 2;      while (1) {         if ((result - 1) * (result - 1) >= i) {             tail = result - 1;             result = (head + tail) / 2;         } else if ( i > result * result) {             head = result + 1;             result = (head + tail) / 2;         } else {             return result * result;         }     }     

一般来说，程序员面试答到这里就过关了，但是作为一个掌握了数学这个伟大工具的程序员，我们还知道一个方法叫做牛顿法。这道题本质上还是求sqrt，我们可以利用牛顿法逼近，同时把数据处理依然控制在整型范围（避免使用浮点数）。由于牛顿法逼近sqrt(i)可能从左也可能从右，同时因为我们做的都是整型计算，可能会出现误差问题，在测试的时候我们同时检查两个数。

       uint32_t test(uint32_t input, uint32_t result) {     if (result >= (1 << 16)) {         // 这里也要注意overflow的问题         return 0;     } else if ((input > (result-1) * (result-1)) && (input <= result * result)) {         return result;     } else if (input > result * result && input <= (result + 1) * (result + 1)) {         return result + 1;     }     return 0; }  uint32_t newton(uint32_t i) {     uint32_t guess_val = 1;     uint32_t loop = 0;     while (1) {         uint32_t result = test(i, guess_val);         loop += 1;         if (result) {             return result * result;         } else {             guess_val = (i / guess_val + guess_val) / 2;         }     } }     

既然我们函数都写出来了，不妨跑一个benchmark测试吧！为了不等太久，我们先把计算数量级设置到(1<<22)。我们对1到(1<22)之间的所有整数去计算，看看三个算法分别需要多久。

首先出场的是我们的naive选手，经过了一通狂跑，他取得了13.559s的好成绩

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m13.559s user 0m13.559s sys 0m0.000s     

接下来大摇大摆目中无人地出场的是我们的工业界领袖bin_search选手，他以碾压的姿态，取得了0.198s的成绩，完爆naive选手。

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m0.199s user 0m0.199s sys 0m0.000s     

最后出场的就是万众瞩目的学术界新型，newton选手，他在摩拳擦掌之后，取得了——0.513秒的成绩。

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m0.513s user 0m0.513s sys 0m0.000s     

什么！我不信！不阔能！怎么可能牛顿法没有愚蠢的二分法好呢？

别着急，我们慢慢分析。

首先，应newton选手的要求，我们把数据级别提升到了(1<<25)的级别，然而bin_search依然以相似的优势领先

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m1.574s user 0m1.570s sys 0m0.004s  gaotian@cercis:/tmp/funprog$ time ./test   real 0m4.657s user 0m4.657s sys 0m0.000s     

newton选手思考了一下，他觉得自己的差距可能是在test函数上。这个函数本身有消耗，同时在大部分情况下都要走过所有的判断，所以他决定改写一下这个函数

       static inline uint32_t test(uint32_t input, uint32_t result) {     if ((result >= (1 << 16)) ||              (result+1) * (result+1) < input ||             (result-1) * (result-1) >= input) {         return 0;     } else if (input <= result * result) {         return result;     } else {         return result + 1;     } }     

沾沾自喜的牛顿选手重新提交了程序，结果是——

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m4.671s user 0m4.670s sys 0m0.000s     

甚至还慢了一点……

看着哇哇大哭的newton选手，来自Green Hills的MULTI老师缓缓走来，对他说，孩子，听我一句话，叫做“Never optimize before profilng”。当你不知道你程序的瓶颈在哪儿的时候，你要先找到自己程序的问题。来，请欣赏我的表演。

Green Hills的MULTI把newton选手和bin_search选手的程序同时编译了，在编译的时候打开了coverage功能，然后运行了一下。

可以看到，newton选手的方法在收敛次数上和bin_search是相似的，516m次 vs 503m次，甚至newton还多一些。这和我们的幻想并不一致。

其原因是什么呢？很简单，尽管newton法可以不断提升精度，即结果离理论值的距离，但是在离结果较远的时候，它的收敛速度并不算优异。而对这个问题来说，远方的收敛速度才是决定性的，在收敛到+-1之后，结果就出来了，而这里才是newton法开始发挥的空间。

我们可以简单地做个数学计算。bin_search在开始阶段从x逼近sqrt(x)的时候，趋势是x/2, x/4, x/8。而newton法是(i/x + x/2)，也就是除二之后还要加一个数。这个逼近速度是要逊于bin_search的（当然实际上因为这个数比较小，是差不多的）。只有当bin_search overshoot了之后，newton的渐进优势才能体现出来。

同时其实我们可以知道，用newton method的时候，如果可以事先取得一个比较好的猜测，那逼近就会变得容易很多。所以我们可以通过如下的方式去先“猜”一个数。我们把i不断除2，直到除到它的平方比i小为止。然后我们以此作为第一个猜测。

       uint32_t guess(uint32_t i) {     int len = 0;     uint32_t temp = i;     while (temp * temp > i) {         temp >>= 1;     }      return temp; }     

       gaotian@cercis:/tmp/funprog$ time ./test   real 0m1.611s user 0m1.611s sys 0m0.000s     

于是newton在数学的帮助下得到了一个和bin_search速度接近的代码。为什么速度接近呢？仔细想一下，这个猜测的过程，其实就是bin_search的前半部分啊！

天真的我曾以为，故事到了这里就有了结尾。

我没有去思考为什么在复制了bin_search的前半部分之后，newton还是慢一些。我想当然地把因素归结到newton本身的复杂机制，但是——我错了，我把代码写错了，而且是一个我在前面强调了好几次的地方……overflow……

我们把guess函数重新写一下，考虑进去overflow的因素

       uint32_t guess(uint32_t i) {     int len = 0;     uint32_t temp = i;     if (temp >= (1<<16)) {         temp = (1<<16) - 1;     }     while (temp * temp > i) {         temp >>= 1;     }      return temp; }     

然后再跑一下。

       gaotian@cercis:/tmp/funprog$ time ./test  real    0m1.051s user    0m1.051s sys     0m0.000s     

牛顿威武！

不过细心的小伙伴应该看出来了，我们这里其实耍赖皮了，我们直接默认开方之后的数最大就是(1<<16)。如果newton可以这么玩赖，那bin_search当然也可以。正当我回去准备把bin_search的代码也加入这个赖皮因素再比较的时候，我才意识到——我已经做了这件事了……

bin_search里已经把tail值在i太大的时候锁定在(1<<16)，而我没意识到这件事！而这个优化很可能才是bin_search之前领先的核心因素，它少做了好多个iteration啊！

这个故事告诉我们，即便你觉得自己花了很多时间和精力把一个程序研究透了，你依然可能有不经意间留下的bug和错误，等着你未来打自己的脸。

认同（划掉）。

不认同！！