forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsqrt_precision_factor.py
More file actions
36 lines (25 loc) · 848 Bytes
/
sqrt_precision_factor.py
File metadata and controls
36 lines (25 loc) · 848 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
"""
Square Root by Newton's Method
Compute the square root of a positive number using Newton's method
(Babylonian method) with a configurable precision factor.
Reference: https://en.wikipedia.org/wiki/Newton%27s_method#Square_root
Complexity:
Time: O(log(1/epsilon)) iterations for convergence
Space: O(1)
"""
from __future__ import annotations
def square_root(n: float, epsilon: float = 0.001) -> float:
"""Compute the square root of n with maximum absolute error epsilon.
Args:
n: A positive number.
epsilon: Maximum allowed absolute error.
Returns:
An approximation of sqrt(n).
Examples:
>>> abs(square_root(5, 0.001) - 2.236) < 0.002
True
"""
guess = n / 2
while abs(guess * guess - n) > epsilon:
guess = (guess + (n / guess)) / 2
return guess