Heron method in Python

Question

Heron's method generates a sequence of numbers that represent better and better approximations for √n. The first number in the sequence is an arbitrary guess; every other number in the sequence is obtained from the previous number prev using the formula:

    (1/2)*(prev+n/prev)

I am supposed to write a function heron() that takes as input two numbers: n and error. The function should start with an initial guess of 1.0 for √n and then repeatedly generate better approximations until the difference (more precisely, the absolute value of the difference) between successive approximations is at most error.

    usage:
    >>> heron(4.0, 0.5)
    2.05
    >>> heron(4.0, 0.1)
    2.000609756097561

this is a bit tricky, but I will need to keep track of four variables:

    # n, error, prev and current

I will also need a while loop with the condition:

    ((current - prev) > error):

A general rule for the while loop is that:

    # old current goes into new prev

So this is what I got so far, it's not much because to start with I don't know how to incorporate the 'if' statement under the while loop.

def heron(n, error):
    guess = 1
    current = 1
    prev = 0
    while (current - prev) > error:
        previous==1/2*(guess+n/guess):
           print (previous) # just a simple print statement
                            # in order to see what i have so far

Can someone give me a few pointers in the right direction please?

thank you

Answer 1

If you don't want to use generators then the simplest would be:

def heron(n, error):
    prev, new = 1.0, 0.5 * (1 + n)
    while abs(new - prev) > error:
        prev, new = new, 0.5 * (new + n/new)
    return new

You can also generate an "infinite" sequence of heron numbers:

def heron(n):
    prev = 1.0
    yield prev, float('inf')
    while True:
        new = 0.5 * (prev + n/prev)
        error = new - prev
        yield new, error
        prev = new

Now you can print so many numbers as you like, for example:

list(islice(heron(2), 3))     # First 3 numbers and associated errors

Generate as long as the error is greater than 0.01:

list(takewhile(lambda x:x[1] > 0.01, heron(2)))

Answer 2

Just to build on @elyase's answer, here's how you would get the arbitrary precision square root from the heron number generator they have provided. (the generator just gives the next number in the heron sequence)

def heron(n): ### posted by elyase
    a = 1.0
    yield a
    while True:
        a = 0.5 * (a + n/a)
        yield a

def sqrt_heron(n, err):
    g = heron(n)
    prev = g.next()
    current = g.next()
    while( (prev - current) > err):
        prev = current
        current = g.next()
        print current, prev
    return current

print sqrt_heron(169.0,0.1)

Aside from python syntax, the thing that may be messing you up is that you need two guesses calculated from your initial guess to get started, and you compare how far apart these two guesses are. The while condition should be (prev - current) > err not (current - prev) > err since we expect the previous guess to be closer to the square (and therefore larger) than the current guess which should be closer to the square root. Since the initial guess could be any positive number, we need to calculate two iterations from it, to ensure that current will be less than prev.

Answer 3

The other answers up as I write this are using a Python generator function. I love generators but those are overkill for this simple problem. Below, solutions with simple while loops.

Comments below the code. heron0() is what you asked for; heron() is my suggested version.

def heron0(n, error):
    guess = 1.0
    prev = 0.0
    while (guess - prev) > error:
        prev = guess
        guess = 0.5*(guess+n/guess)
        print("DEBUG: New guess: %f" % guess)
    return guess

def _close_enough(guess, n, allowed_error):
    low = n - allowed_error
    high = n + allowed_error
    return low <= guess**2 <= high

def heron(n, allowed_error):
    guess = 1.0
    while not _close_enough(guess, n, allowed_error):
        guess = 0.5*(guess+n/guess)
        print("DEBUG: New guess: %f" % guess)
    return guess

print("Result: %f" % heron0(4, 1e-6))
print("Result: %f" % heron(4, 1e-6))

Comments:

• You don't really need both guess and current. You can use guess to hold the current guess.

• I don't know why you were asking about putting an if statement in the while loop. In the first place, it is easy: you just put it in, and indent the statement(s) that are under the if. In the second place, this problem doesn't need it.

• It's easy and fast to detect whether guess is close to prev. But I think for numerical accuracy, it would be better to directly test how good a square root guess actually is. So, square the value of guess and see if that is close to n. See how in Python it is legal to test whether a value is, at the same time, greater than or equal to a lower value and also less than or equal to a high value. (The alternate way to check: abs(n - guess**2) <= allowed_error)

• In Python 2.x, if you divide an integer by an integer you will probably get an integer result. Thus 1/2 can very possibly have a result of 0. There are a couple of ways to fix that, or you can run your program in Python 3.x which guarantees that 1/2 returns 0.5, but it's simple to make your starting value for guess be a floating-point number.

Answer 4

I think this meets your requirements (note: I wrote it with python 2.7.10): it doesn't assume a guess of 1 and it takes takes 'num' and 'tolerance' as arguments for 'n' and 'error'. Also, it doesn't use variables "prev" and "current" or a while loop - are those part of your requirements, or your thoughts regarding a solution?

def heron(num, guess, tolerance):
    if guess**2 != num:
        ##print "guess =", guess
        if abs(float(num) - float(guess)**2) > float(tolerance):
            avg_guess = 0.5 * (float(guess) + (float(num) / float(guess)))
            return heron(num, avg_guess, tolerance)
        print "Given your tolerance, this is Heron's best guess:", guess
    else:
        print guess, "is correct!"

Uncomment the print cmd if you want to see the progression of guesses.

Answer 5

I was dealing with the same problem and not many tools to solve it since my knowledge in Python is very limited.
I came up with this solution that is not very elegant nor advanced, but it solves the problem using Heron's algorithm. Just want it to share it here:

print("Please enter a positive integer 'x' to find its square root.")
x = int(input("x ="))
g = int(input("What's your best guess: "))
results = [g]
if g * g == x:
    print("Good guess! The square root of", x, "is", g)
else:
    g = (g + (x / g)) / 2
    results.append(g)
    while results[-1] != results[-2]:
        g = (g + (x / g)) / 2
        results.append(g)
    else:
        print(results)
        print("Not quite. The square root of", x, "is", results[-1])