Finding the square root using Newton's method

问题:

I'm working to finish a math problem that approximates the square root of a number using Newton's guess and check method in Python. The user is supposed to enter a number, an initial guess for the number, and how many times they want to check their answer before returning. To make things easier and get to know Python (I've only just started learning the language a couple of months ago) I broke it up into a number of smaller functions; the problem now, though, is that I'm having trouble calling each function and passing the numbers through.

Here is my code, with comments to help (each function is in order of use):

# This program approximates the square root of a number (entered by the user)
# using Newton's method (guess-and-check). I started with one long function,
# but after research, have attempted to apply smaller functions on top of each
# other.
# * NEED TO: call functions properly; implement a counting loop so the
# goodGuess function can only be accessed the certain # of times the user
# specifies. Even if the - .001 range isn't reached, it should return.

# sqrtNewt is basically the main, which initiates user input.

def sqrtNewt():
    # c equals a running count initiated at the beginning of the program, to
    # use variable count.
    print("This will approximate the square root of a number, using a guess-and-check process.")
    x = eval(input("Please type in a positive number to find the square root of: "))
    guess = eval(input("Please type in a guess for the square root of the number you entered: "))
    count = eval(input("Please enter how many times would you like this program to improve your initial guess: ")) 
    avg = average(guess, x)
    g, avg = improveG(guess, x)
    final = goodGuess(avg, x)
    guess = square_root(guess, x, count)
    compare(guess, x)


# Average function is called; is the first step that gives an initial average,
# which implements through smaller layers of simple functions stacked on each
# other.
def average(guess, x) :
    return ((guess + x) / 2)

# An improvement function which builds upon the original average function.
def improveG(guess, x) :
    return average(guess, x/guess)

# A function which determines if the difference between guess X guess minus the
# original number results in an absolute vale less than 0.001. Not taking
# absolute values (like if guess times guess was greater than x) might result
# in errors
from math import *
def goodGuess(avg, x) :
    num = abs(avg * avg - x)
    return (num < 0.001)

# A function that, if not satisfied, continues to "tap" other functions for
# better guess outputs. i.e. as long as the guess is not good enough, keep
# improving the guess.
def square_root(guess, x, count) :
    while(not goodGuess(avg, x)):
        c = 0
        c = c + 1
        if (c < count):
            guess = improveG(guess, x)
        elif (c == count):
            return guess
        else :
            pass

# Function is used to check the difference between guess and the sqrt method
# applied to the user input.
import math
def compare(guess, x):
    diff = math.sqrt(x) - guess
    print("The following is the difference between the approximation") 
    print("and the Math.sqrt method, not rounded:", diff)

sqrtNewt()

Currently, I get this error: g, avg = improveG(guess, x) TypeError: 'float' object is not iterable. The final function uses the final iteration of the guess to subtract from the math square root method, and returns the overall difference. Am I even doing this right? Working code would be appreciated, with suggestions, if you can provide it. Again, I'm a newbie, so I apologize for misconceptions or blind obvious errors.

回答1:

Implementation of the newton method:

It should be fairly easy to add little tweaks to it when needed. Try, and tell us when you get stuck.

from math import *
def average(a, b):
    return (a + b) / 2.0
def improve(guess, x):
    return average(guess, x/guess)
def good_enough(guess, x):
    d = abs(guess*guess - x)
    return (d < 0.001)
def square_root(guess, x):
    while(not good_enough(guess, x)):
        guess = improve(guess, x)
    return guess
def my_sqrt(x):
    r = square_root(1, x)
    return r

>>> my_sqrt(16)
4.0000006366929393

NOTE: you will find enough exaples on how to use raw input here at SO or googling, BUT, if you are counting loops, the c=0 has to be outside the loop, or you will be stuck in an infinite loop.

Quiqk and dirty, lots of ways to improve:

from math import *
def average(a, b):
    return (a + b) / 2.0
def improve(guess, x):
    return average(guess, x/guess)
def square_root(guess, x, c):
    guesscount=0
    while guesscount < c :
        guesscount+=1
        guess = improve(guess, x)
    return guess
def my_sqrt(x,c):
    r = square_root(1, x, c)
    return r

number=int(raw_input('Enter a positive number'))
i_guess=int(raw_input('Enter an initial guess'))
times=int(raw_input('How many times would you like this program to improve your initial guess:'))    
answer=my_sqrt(number,times)

print 'sqrt is approximately ' + str(answer)
print 'difference between your guess and sqrt is ' + str(abs(i_guess-answer))

回答2:

The chosen answer is a bit convoluted...no disrespect to the OP.

For anyone who ever Googles this in the future, this is my solution:

def check(x, guess):
    return (abs(guess*guess - x) < 0.001)

def newton(x, guess):
    while not check(x, guess):
        guess = (guess + (x/guess)) / 2.0
    return guess

print newton(16, 1)

回答3:

Here's a rather different function to compute square roots; it assumes n is non-negative:

def mySqrt(n):
    if (n == 0):
        return 0
    if (n < 1):
        return mySqrt(n * 4) / 2
    if (4 <= n):
        return mySqrt(n / 4) * 2
    x = (n + 1.0) / 2.0
    x = (x + n/x) / 2.0
    x = (x + n/x) / 2.0
    x = (x + n/x) / 2.0
    x = (x + n/x) / 2.0
    x = (x + n/x) / 2.0
    return x

This algorithm is similar to Newton's, but not identical. It was invented by a Greek mathematician named Heron (his name is sometimes spelled Hero) living in Alexandria, Egypt in the first century (about two thousand years ago). Heron's recurrence formula is simpler than Newton's; Heron used x' = (x + n/x) / 2 where Newton used x' = x - (x^2 - n) / 2x.

The first test is a special case on zero; without it, the (n < 1) test causes an infinite loop. The next two tests normalize n to the range 1 < n <= 4; making the range smaller means that we can easily compute an initial approximation to the square root of n, which is done in the first computation of x, and then "unroll the loop" and iterate the recurrence equation a fixed number of times, thus eliminating the need for testing and recurring if the difference between two successive loops is too large.

By the way, Heron was a pretty interesting fellow. In addition to inventing a method for calculating square roots, he built a working jet engine, a coin-operated vending machine, and lots of other neat stuff!

You can read more about computing square roots at my blog.

回答4:

it shouldnt have to be that complicated i wrote this up

def squareroot(n,x):
final = (0.5*(x+(n/x)))
print (final)
for i in range(0,10):
    final = (0.5*(final+(n/final)))
    print (final)

or you could change it to be like this

n = float(input('What number would you like to squareroot?'))
x = float(input('Estimate your answer'))
final = (0.5*(x+(n/x)))
print (final)
for i in range(0,10):
    final = (0.5*(final+(n/final)))
    print (final)

回答5:

All you need to know is the nth term in the sequence. From the Leibniz series, we know this is ((-1)**n)/((2*n)+1). Just sum this series for all i with an initial condition of zero and you're set.

def myPi(n):

pi=0
for i in range(0,n):
    pi=pi+((-1)**i)/((2*i)+1)
return 4*pi
print (myPi(10000))