To find the square root of a real number n, we can use the Binary Search method due to its efficiency in narrowing down the range step by step. Alternatively, the Newton-Raphson method is also widely used for its iterative approach.
Here is the approach:
Set the initial range from 0 to n (or 0 to 1 if n < 1).
Continuously narrow down the range by checking the middle point.
If mid*mid is close enough to n, return mid.
Adjust the range based on whether mid*mid is greater or smaller than n.
If x is an approximation of sqrt(n), then n/x is an approximation from the other side. Averaging them, (x + n/x)/2, produces a better approximation. Repeating this update quickly converges to sqrt(n).
classSolution {
public:double sqrt(double n, double eps =1e-7) {
if (n <0) throw std::domain_error("n must be non-negative");
if (n ==0.0|| n ==1.0) return n;
double x = (n >=1.0) ? n /2.0: n;
while (std::abs(x * x - n) > eps) {
x = (x + n / x) /2.0;
}
return x;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
packagemainimport (
"errors""math")
funcsqrt(n, epsfloat64) (float64, error) {
ifn < 0 { return0, errors.New("n must be non-negative") }
ifn==0||n==1 { returnn, nil }
x:=nifn>=1 { x = n/2 }
formath.Abs(x*x-n) > eps {
x = (x+n/x) /2 }
returnx, nil}
1
2
3
4
5
6
7
8
9
10
11
classSolution {
publicdoublesqrt(double n, double eps) {
if (n < 0) thrownew IllegalArgumentException("n must be non-negative");
if (n == 0 || n == 1) return n;
double x = (n >= 1.0) ? n / 2.0 : n;
while (Math.abs(x * x - n) > eps) {
x = (x + n / x) / 2.0;
}
return x;
}
}
1
2
3
4
5
6
7
8
9
10
11
objectSolution {
funsqrt(n: Double, eps: Double = 1e-7): Double {
require(n >=0) { "n must be non-negative" }
if (n ==0.0|| n ==1.0) return n
var x = if (n >=1.0) n / 2.0else n
while (kotlin.math.abs(x * x - n) > eps) {
x = (x + n / x) / 2.0 }
return x
}
}
1
2
3
4
5
6
7
8
9
10
classSolution:
defsqrt(self, n: float, eps: float =1e-7) -> float:
if n <0:
raiseValueError('n must be non-negative')
if n ==0.0or n ==1.0:
return n
x = n /2.0if n >=1.0else n
while abs(x * x - n) > eps:
x = (x + n / x) /2.0return x
1
2
3
4
5
6
7
8
9
10
11
12
pubstructSolution;
impl Solution {
pubfnsqrt(n: f64, eps: f64) -> f64 {
if n <0.0 { panic!("n must be non-negative") }
if n ==0.0|| n ==1.0 { return n }
letmut x =if n >=1.0 { n /2.0 } else { n };
while (x * x - n).abs() > eps {
x = (x + n / x) /2.0;
}
x
}
}
⏰ Time complexity: O(k) where k is the number of iterations required to reach epsilon. Newton’s method converges quadratically, so k is typically very small.