A guessing game

Here is a simple demonstration program that shows how to use user input and a while loop. The program implements a simple guessing game in which the user has to guess a secret number that falls in the range from 1 to 100.

# Simple guessing game
secret = 22

print("I am thinking of a number between 1 and 100.")
guess = input("Enter your guess: ")
guess = int(guess)

count = 1
while guess != secret and count < 5:
    if guess < secret:
        print("Your guess is too low.")
    else:
        print("Your guess is too high.")
    count = count + 1
    guess = input("Enter your guess: ")
    guess = int(guess)
    
if guess == secret:
    print("Correct!")
else:
    print("Sorry, the secret number is "+str(secret))

Newton's Method

Newton's method is a method for finding roots of functions. Given a differentiable function f(x) we would like find a root of f, that is, a value of x such that f(x) = 0.

The method consists of the following steps:

  1. Pick a point x0 close to a root. Find the corresponding point (x0 , f(x0)) on the curve.
  2. Draw the tangent line to the curve at that point, and see where it crosses the x-axis.
  3. The crossing point, x1, is your next guess. Repeat the process starting from that point until you are satisfied that you are close enough to the root.

Mathematical details

We pick a point

(x0, f(x0))

on the curve and find the equation of the tangent line at that point. The slope of the tangent line at that point is

The tangent line has general form

This line intersects the x-axis when y = 0.

To repeat the process we just have to feed the point x1 back into the last formula to generate the next approximation for the root:

Each time we generate another approximation we can easily test to see how close that approximation is to the root by simply plugging that back into the function f. Once |f(xn)| drops below a preset tolerance we can stop the iteration.

Program

Here is the code for a Python program that uses Newton's method to find a root for the function

f(x) = x4 + 2 x3 - 14 x2 + 2 x + 1

This function has a positive real root near about 0.4. To find this root we will write a function that uses the Newton iteration with the function f(x) and its derivative

To make computing the polynomials f(x) and f(x) more efficient we will use a special trick called Horner's rule to evaluate the polynomials. Can you see how Horner's rule works?

# Program to find the roots of f(x)= x^4+2 x^3-14 x^2+2 x+1
# by Newton's method

x = input("Enter a starting guess for the root: ")
x = float(x)

fx = (((x+2)*x-14)*x+2)*x + 1

tolerance = 10e-6

while fx < -tolerance or fx > tolerance:
    # Compute f'(x)
    fpx = ((4*x+6)*x-28)*x+2
    # Do one round of Newton's method
    x = x - fx/fpx
    fx = (((x+2)*x-14)*x+2)*x + 1
    
print("The root estimate is " + str(x))