forked from timoncui/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSqrt_X.cpp
More file actions
42 lines (31 loc) · 678 Bytes
/
Sqrt_X.cpp
File metadata and controls
42 lines (31 loc) · 678 Bytes
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
40
41
42
/*
Author: Timon Cui, [email protected]
Title: Sqrt X
Description:
Implement int sqrt(int x).
Compute and return the square root of x.
Difficulty rating:
Source:
Notes:
Newton's method:
y = r^2 - x = 0
r' = r - y/derivative(y, r) = r - (r^2 - x) / 2r = r / 2 + x / 2r
*/
#include "utils.hpp"
using namespace std;
class Solution {
public:
int sqrt(int x) {
if (x <= 0) return 0;
double half_x = x / 2.0;
double r = 0.5 + half_x;
while (abs(r * r - x) > 1e-6) r = r / 2 + half_x / r;
return floor(r);
}
};
int main() {
Solution s;
eq(0, sqrt(1), 1);
eq(1, sqrt(8192), 90);
eq(2, sqrt(25), 5);
}