# 面试题精选:求根号2简单？高级算法你肯定不会

## 二分查找

public class BSearch {
static double sqrt2 = 1.4142135624;
static double delta = 0.0000000001;
public static void main(String[] args) {
double l = 1.0;
double r = 2.0;
int cnt = 0;
while (l < r) {
double mid = (l + r) / 2;
if (Math.abs(l - sqrt2) < delta) {
break;
}
if (mid * mid > 2.0) {
r = mid;
} else {
l = mid;
}
cnt++;
}
System.out.println("经过" + cnt + "次迭代后得" + l);
}
}
经过34次迭代后得1.4142135623260401

## 牛顿迭代

$$x_{1}=x_{0}-\frac{f\left(x_{0}\right)}{f^{\prime}\left(x_{0}\right)} = x_0 - \frac{x_0^2-2}{2x_0}$$

public class NewtonMethod {
static double sqrt2 = 1.4142135624;
static double delta = 0.0000000001;
public static void main(String[] args) {
double x = 2.0;
int cnt = 0;
while (Math.abs(x - sqrt2) > delta){
x = x - (x*x - 2)/(2*x);
cnt++;
}
System.out.println("经过" + cnt + "次迭代后得" + x);
}
}
经过4次迭代后得1.4142135623746899  

Benchmark           Mode  Cnt         Score   Error  Units
Test.NewtonMethod  thrpt    2  96292165.813          ops/s
Test.bSearch       thrpt    2  11856462.059          ops/s

## 神奇的数字0x5f3759df

float InvSqrt(float x)
{
float xhalf = 0.5f*x;
int i = *(int*)&x;
i = 0x5f3759df - (i >> 1);
x = *(float*)&i;
x = x*(1.5f - xhalf*x*x);
return x;
}

public class CarmackMethod {
public static void main(String[] args) {
float x = 2.0f;
float xhalf = 0.5f*x;
//        int i = *(int*)&x;
int i= Float.floatToRawIntBits(x);
i = 0x5f3759df - (i >> 1);
//        x = *(float*)&i;
x = Float.intBitsToFloat(i);
x = x*(1.5f - xhalf*x*x);
System.out.println(1.0/x);
}
}
1.4145671304934657

Benchmark            Mode  Cnt          Score   Error  Units
Test.CarmackMethod  thrpt    2  111286742.330          ops/s
Test.bSearch        thrpt    2   58705907.393          ops/s
Test.NewtonMethod   thrpt    2  110232331.339          ops/s

## 各种编程语言是如何实现sqrt?

  sqrtsd %1, %0" : "=x" (res) : "xm" (x)

__生活处处有惊喜__，当我打开python math模块的源码时，没有发现浮点数的求根(估计也是直接用的CPU级指令)，但我发现了一个更骚的对64位整数求根的操作，所以这里再补充介绍一个python的近似求根算法。

## python中的_approximate_isqrt()

_approximate_isqrt(uint64_t n)
{
uint32_t u = 1U + (n >> 62);
u = (u << 1) + (n >> 59) / u;
u = (u << 3) + (n >> 53) / u;
u = (u << 7) + (n >> 41) / u;
return (u << 15) + (n >> 17) / u;
}

    def isqrt(n):
"""
Return the integer part of the square root of the input.
"""
n = operator.index(n)
if n < 0:
raise ValueError("isqrt() argument must be nonnegative")
if n == 0:
return 0
c = (n.bit_length() - 1) // 2
a = 1
d = 0
for s in reversed(range(c.bit_length())):
# Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2
e = d
d = c >> s
a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a
return a - (a*a > n)

## 引用链接

[1] 牛顿迭代法: https://baike.baidu.com/item/...
[2] 卡马克快速平方根倒数算法: http://jcf94.com/2016/01/14/2...