浮点数开根


2019-02-23

给你讲个鬼故事。

有一只神犇叫 Wzp,模拟赛时出了一道计算几何题精度开到了 1e-13

题目大意就是给你一个 \(\Delta ABC\)\(n(n\le 1000)\) 个向量,你可以在其中选至多 \(k\) 个作用在 \(A\) 上,使最终得到的三角形周长最长。特别的,这个三角形可以退化成一条线,其实只要算 \(AB+BC+AC\) 就可以了。

其中所有给出的数据(包括向量的 \(x, y\))都是整数。

正解在这里就不说了我才不会告诉你是因为我不会做这道题,重点是那个细节,也就是 1e-13 的精度应该怎么整。

重点就是那个 sqrt,这玩意考场上测了一下(用 long double)精度大概只有 \(10^{-8}\sim 10^{-9}\),直接悲惨爆 0……

有一个很妙的 trick,我们设需要计算 \(s=\sqrt{x}\),我们设 \(s\) 的整数部分是 \(a\),小数部分是 \(b\),我们有:

\[ \begin{aligned} x&=(a+b)^2\\ &=a^2+b^2+2ab\\ &=a^2+b(a+b)+ab\\ &=a^2+bs+ab\\ &=a^2+b(s+a) \end{aligned} \]

所以:

\[ \begin{aligned} b=\frac{x-a^2}{s+a} \end{aligned} \]

其中的 s 直接调用 sqrt() 即可。

这样我们就可以用一个 long long 和一个 double(甚至不用 long double)来表示浮点数,精度也会高很多。

Cite this post

@misc{pu2019floatingpointsqrt,
  author = {Pu, Fanyi},
  title  = {浮点数开根},
  year   = {2019},
  month  = {2},
  url    = {https://pufanyi.com/blog/floating-point-sqrt}
}