square root Algorithm
The square root algorithm is a mathematical method used to find the square root of a number, which is a value that, when multiplied by itself, equals the given number. There are several different algorithms that can be used to calculate square roots, such as the Babylonian method, the Newton-Raphson method, and the digit-by-digit method. These algorithms have been used since ancient times to find the square root of a number, and they are still widely used in modern mathematics and computer programming for various calculations.
One of the most well-known square root algorithms is the Babylonian method, also known as Heron's method. This iterative method involves making an initial guess for the square root and then refining that guess using a series of calculations. The basic idea is to take an average of the current guess and the quotient of the number divided by the current guess. This process is repeated until the difference between successive guesses is minimal or within a desired level of accuracy. The Newton-Raphson method is another popular algorithm that uses calculus to refine the estimate of the square root. The digit-by-digit method calculates the square root one digit at a time, starting from the leftmost digit, making it well-suited for manual calculations or in situations where only a few digits of the square root are needed.
import math
def fx(x: float, a: float) -> float:
return math.pow(x, 2) - a
def fx_derivative(x: float) -> float:
return 2 * x
def get_initial_point(a: float) -> float:
start = 2.0
while start <= a:
start = math.pow(start, 2)
return start
def square_root_iterative(
a: float, max_iter: int = 9999, tolerance: float = 0.00000000000001
) -> float:
"""
Square root is aproximated using Newtons method.
https://en.wikipedia.org/wiki/Newton%27s_method
>>> all(abs(square_root_iterative(i)-math.sqrt(i)) <= .00000000000001 for i in range(0, 500))
True
>>> square_root_iterative(-1)
Traceback (most recent call last):
...
ValueError: math domain error
>>> square_root_iterative(4)
2.0
>>> square_root_iterative(3.2)
1.788854381999832
>>> square_root_iterative(140)
11.832159566199232
"""
if a < 0:
raise ValueError("math domain error")
value = get_initial_point(a)
for i in range(max_iter):
prev_value = value
value = value - fx(value, a) / fx_derivative(value)
if abs(prev_value - value) < tolerance:
return value
return value
if __name__ == "__main__":
from doctest import testmod
testmod()
