开平方算法

数学

$\sqrt n$ 可以用如下方法计算。


例子

假设要求$\sqrt{13}$的粗略值。

我们可以很简单地知道 $3<\sqrt{13}<4$。

所以我们设:

这里 $x\in[0,1]$。

把 $(1)$ 式左右平方,得:

因为 $x\in[0,1]$,$x^2$ 较小,可以忽略,因此有

把 $x$ 解出来,得到 $x=\dfrac{2}{3}$。

我们再次假设:

左右平方,忽略 $x^2$,得到:

解之得:

至此我们估算出的 $\sqrt{13}$ 约等于 $3+\dfrac{2}{3}-\dfrac{2}{33}\approx3.60607\approx3.60555\approx\sqrt{13}$。

如果一直这样计算,估算的 $\sqrt{13}$ 的精度会越来越高。


代码

用计算机实现这段操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

int wd, t;
double apx = 0;
map<double, bool> mem;

int main()
{
cin >> wd;
if (wd < 0)
{
printf("Num shouldn\'t be negative.");
return 0;
}
for (apx = 1; apx * apx <= wd; apx++);
apx--;
// wd = apx * apx + 2 * apx * x
getchar();
while (true)
{
apx += (wd - apx * apx) / (2 * apx);
if (mem[apx])
{
printf("This is my best...\n");
break;
}
printf("sqrt(%d) = %.14lf", wd, apx);
getchar();
mem[apx] = true;
}
return 0;
}

本文作者:Xecades

本文链接:https://blog.xecades.xyz/articles/sqrt/

文章默认使用 CC BY-NC-SA 4.0 协议进行许可,使用时请注意遵守协议。

评论