AI工具人

# 大厂面试题:求根号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 &lt; r) {
double mid = (l + r) / 2;
if (Math.abs(l - sqrt2) &lt; delta) {
break;
}
if (mid * mid &gt; 2.0) {
r = mid;
} else {
l = mid;
}
cnt++;
}
System.out.println(&quot;经过&quot; + cnt + &quot;次迭代后得&quot; + 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) &gt; delta){
x = x - (x*x - 2)/(2*x);
cnt++;
}
System.out.println(&quot;经过&quot; + cnt + &quot;次迭代后得&quot; + 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*)&amp;x;
i = 0x5f3759df - (i &gt;&gt; 1);
x = *(float*)&amp;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*)&amp;x;
int i= Float.floatToRawIntBits(x);
i = 0x5f3759df - (i &gt;&gt; 1);
//        x = *(float*)&amp;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&quot; : &quot;=x&quot; (res) : &quot;xm&quot; (x)

## python中的_approximate_isqrt()

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

    def isqrt(n):
&quot;&quot;&quot;
Return the integer part of the square root of the input.
&quot;&quot;&quot;
n = operator.index(n)
if n &lt; 0:
raise ValueError(&quot;isqrt() argument must be nonnegative&quot;)
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 &lt; (n &gt;&gt; 2*(c - d)) &lt; (a+1)**2
e = d
d = c &gt;&gt; s
a = (a &lt;&lt; d - e - 1) + (n &gt;&gt; 2*c - e - d + 1) // a
return a - (a*a &gt; n)

## 引用链接

[2] 卡马克快速平方根倒数算法: http://jcf94.com/2016/01/14/2016-01-14-carmack/
[5] 这条汇编指令: https://code.woboq.org/userspace/glibc/sysdeps/x86_64/fpu/e_sqrt.c.html
[7] python math模块: https://github.com/python/cpython/blob/master/Modules/mathmodule.c