java - Cracking the Code book 平方根算法中的整数范围

Question

java中有一个破解密码本求平方根的算法如下:

int sqrt(int n) {
  return sqrt_helper(n, 1, n);
}

int sqrt_helper(int n, int min, int max) {
  if (max < min) return -1; 
  int guess = (min + max) / 2·,
  if (guess *guess == n) { 
    return guess;
  } else if (guess * guess < n) { 
    return sqrt_helper(n, guess + 1, max); 
  } else {  
    return sqrt_helper(n, min, guess - l); 
  }
}

问题是:

由于 min 和 max 是整数，它们可以是范围内的任何值，即 max = Integer.MAX_VALUE

所以不用担心 guess = (min + max)/2 因为它会超过允许的范围，或者 guess *guess 也是。

Answer 1

有一些简单的方法可以解决这个问题(比如 min + (max - min)/2)。

比较严重的整数溢出问题是guess * guess。您可以更改测试以将 guess 与 n/guess 进行比较，后者速度较慢但通常不会溢出。或者你可以使用一些 hack 来找到一个更好的起点(clz 在这里很有用，如果你有的话)，因为你应该能够找到一个猜测，其平方在可表示整数的范围内.

如果您能够提供 Newton-Raphson algorithm，面试官可能会印象更深刻, 收敛速度极快。