Chapter 3: EXHAUSTIVE AND APPROXIMATE SOLUTIONS
Some Approximation Techniques in Python: Numerical Search Methods and Their Applications
So, What are we talking about today?
Note
- To understand exhaustive enumeration and iterative numerical techniques for approximation
- To study and understand how algorithms use approximations to find square and cube roots
- Compare efficiency of different approximation methods, and some of their limitations
- To explore primality testing using enumeration
- Implement practical Python solutions (code)
Exhaustive Versus Approximation: Two Solution Types
Testing the Prototype
Flowchart: simple_square_root(x)
Example: For x = 25,
tests: 0^2, 1^2, 2^2, 3^2, 4^2, 5^2 = 25 ✓
Be careful!
Example: For x = 26,
tests: 0^2, 1^2, 2^2, 3^2, 4^2, 5^2, 6^2 != 26
(We just passed the correct value!!)
Testing the Prototype
Flowchart: simple_cube_root(x)
Testing the Flowcart
Example: For x = 8,
tests: 0^3, 1^3, 2^3 = 8 ✓
Be careful!
For x = 9, tests: 0^3, 1^3, 2^3, 3^3 != 9
(We just passed the correct value!!)
Flowchart: simple_n_root(x)
Flowchart: exhaustive_sqrt_flowchart(x)
Testing the Prototype
Finding square root of 25
Number of guesses: 500
Square root of 25 is approximately 4.9999999999999384.999999999999938Finding square root of 26
Number of guesses: 510
Square root of 26 is approximately 5.0999999999999365.099999999999936How This Code Works:
Note
Algorithm Steps:
- Start with
ans = 0.0 - Increment by
epsiloneach iteration - Check if
ans²is close enough tox - Stop when within tolerance or exceeded target
Key Variables:
step: How much to increment each guessnum_guesses: Performance counterans: Current approximation
Loop Condition Explained:
abs(ans**2 - x) >= epsilon: Not accurate enough yetans*ans <= x: Haven’t exceeded target (prevents infinite loop)
Why It Works:
- Systematically tests every possible value
- Guaranteed to find solution if it exists
- Simple but inefficient for large numbers
The Fundamental Limitation of Guessing and Checking
These functions use “exhaustive enumeration” over integers:
- Perfect squares/cubes: Have integer roots (4, 9, 16, 25…)
- Non-perfect squares/cubes: Have irrational/decimal roots
Key Insight: The algorithm design assumes the answer is an integer!
Exhaustive Versus Approximation: Two Solution Types
Remember this slide?
Whoops, here’s the right slide.
(Issac Newton)Square Root Approximation with Newton’s Method
def newtons_sqrt(n:float, guess:float = 1.0) -> float:
while abs(n - guess*guess) > .0001:
print(f"n = {n}, guess = {guess}")
print(f" abs(n - guess*guess) = {abs(n - guess*guess)}")
guess = guess - (guess*guess - n)/(2*guess)
print(f" guess = guess - (guess*guess - n)/(2*guess) = {guess}\n")
return guessCube Roots
def newtons_cube_root(n:float, guess:float = 1.0) -> float:
while abs(n - guess*guess*guess) > .0001:
print(f"n = {n}, guess = {guess}")
print(f" abs(n - guess^3) = {abs(n - guess*guess*guess)}")
guess = guess - (guess*guess*guess - n)/(3*(guess*guess))
print(f" guess = guess - (guess*guess*guess - n)/(3*(guess*guess)) = {guess}\n")
return guess
Note
We are getting increasingly closer the actual value. which is determined by the tolerance level (and hence the number of iterations) as specified here by the algorithm’s parameters.
Challenge!
Can you modify the newtons_cube_root() algorithm to find the forth root newtons_4_root()
Hint: Use the general case to create the code.
Challenge 1: Perfect-Square Tester
Task: Write is_perfect_square(n) that returns True if n is a perfect square and False otherwise.
Constraints: Use exhaustive enumeration (counting up).
Challenge 2: Epsilon Square Root
Task: Write approx_sqrt(x, epsilon=0.001) using exhaustive enumeration with a step size of epsilon.
Return the approximation and the number of guesses.
Challenge 3: Count Newton Steps
Task: Write newtons_sqrt_steps(x, guess=1.0, tol=1e-4) that returns 1) the approximation and 2) how many iterations it took.
Challenge 4: Integer Cube Root (No Decimals)
Task: Write int_cube_root(n) that returns the integer cube root if it exists, otherwise returns None.
Use exhaustive enumeration only.
Challenge 5: Compare Methods
Task: Write compare_methods(x) that prints two lines:
- The values of
exhaustive approximation(epsilon = 0.001) and the values of theguessesfor each iteration of “simple_square_root(x)” - Then print the values of
guessesfor each iteration “newtons_sqrt()”
Which algorithm do you suppose is better? Why?
