sqrt_approx.py

import math

"""
I don't include this detail i nthe docstring for approx_sqrt since it's more than what is needed, someone
looking to understand Newton-Raphson will look it up on wikipedia after reading that docstring. But for
your sake Newton-Raphson states that to find the roots of any function f(x) we need an initial guess
called x_0. The further away this guess is from the actual root, the longer it takes. Then we get the 
first approximation, x_1, using:

x_1 = x_0 - f(x0)/f_prime(x0)

Where f_prime is the derivative of f. x_1 is unlikely to be close to the actual root. So we can repeat
this process using our first approximation as the next guess to get the second approximation, x_2, using
 the same function, f:

x_2 = x_1 - f(x_1)/f_prime(x_1)

We repeat this enough the differences between our approximations will eventually become very very small.
So if we define a Tolerance value, T, we say an approximation is good enough if:

|x_N - x_(N-1)| <= T

Or, the absolute difference (or distance) between the current approximation and the guess is less than
or equal to the tolerated distance.

"""


def approx_sqrt(x, guess=10, epsilon=10**-4, last_guess=None):
	"""
	Approximates the square root of a given value using the Newton-Raphson Method of approximating roots
	of a function. We can do this by noting that finding sqrt(C) for some constant C is the same as 
	finding the roots of the equations x^2 = C, or finding the solutions to x^2 - C = 0.
	
	Approximating the positive root of x^2 - C = 0 can be done using the Newton-Raphson method.
	
	:pre:	x is positive
	
	<< For CS 1 students, note: No post-condition necessary. A pre-condition is barely necessary/ >>
	
	:param x: Value to approximate the square root of
	:param guess: Initial guess value, defaults to 10 if not provided
	:param epsilon: The tolerable difference between guesses, once the difference between
					assumptions is below this value, we return the most recent approximation
	:param last_guess: The previous guess, defaults to None as a starting value
	
	:return: The approximation of sqrt(x) according ot the newton-raphson method
	"""
	
	# If we have a previous guess and the difference between the current guess
	# and the last guess is tolerable, return the current guess
	if last_guess is not None and abs(guess - last_guess) <= epsilon:
		return guess
	
	
	f = guess*guess - x					# f(x_0)
	f_prime = 2*guess					# f_prime(x_0)
	next_guess = guess - f/f_prime		# x_1 = x_0 - f(x_0)/f_prime(x_0)
	
	# Continue approximation
	return approx_sqrt(x, next_guess, epsilon, guess)

# Just some pretty-printing.

# Prints the actual value of sqrt(x), x, and the approximation of sqrt(x)
# for x = 1 to 100 in a nice table.
print("sqrt(x)".center(20), ':', "x".center(10), ':', "approx_sqrt(x)".center(20))
for i in range(1, 101):
	exact = str(math.sqrt(i)).ljust(20)
	approx = str(approx_sqrt(i)).ljust(20)
	
	print(exact, ':', str(i).center(10), ':', approx)