1
\$\begingroup\$

Below is the solution:

def approx_deriv(fn, x, dx=0.00001):
    return (fn(x + dx) - fn(x))/dx

def improve(update, isdone, guess=1, max_iterations=100):
    def recur_improve(guess, i):
        if i > max_iterations or isdone(guess):
           return guess
        else:
           return recur_improve(update(guess), i + 1)
    return recur_improve(guess, 1)

def newtons_method(fn, guess =1, max_iterations=100):
    def newtons_update(guess):
        return guess - fn(guess) / approx_deriv(fn, guess)
    def newtons_isdone(guess):
        ALLOWED_ERROR_MARGIN = 0.0000001
        return abs(fn(guess)) <= ALLOWED_ERROR_MARGIN
    return improve(newtons_update, 
                        newtons_isdone, 
                        max_iterations)

def nth_root(rootfunc, x):
    return rootfunc(x)

Test output:

>python -i nth_root.py
>>> def cuberoot(x):
...     return newtons_method(lambda y: y * y * y - x)
...
>>> result = nth_root(cuberoot, 27)
>>> result
3.000000000000141
>>>

My question:

Above is the functional abstraction for finding the \$n_{th}\$ root of a number. Is it possible to improve this abstraction?

\$\endgroup\$
2
  • \$\begingroup\$ Shouldn't that be i > max_iterations or isdone(guess)? \$\endgroup\$
    – jonrsharpe
    Commented Apr 17, 2015 at 14:45
  • \$\begingroup\$ yes, it is or, query edited \$\endgroup\$ Commented Apr 17, 2015 at 15:03

2 Answers 2

1
\$\begingroup\$

First, congratulations for the work you did : one can easily see that you put some thinking into it and as far as I have tested it, it works.

However, I still have a few comments and most of them are about the fact that you might have tried to be too clever.

Indeed, the use of both recursion and nested functions is a bit too much for my brain. Among other things, it took me a while to spot that the guess argument of the newtons_method is not used (and I am not even sure of it, am I right ?). You could make is easier to grasp by using names conveing more meaning.

Here's my attempt to un-nest functions and to change names (I am fully aware that they are not perfect) :

def recur_improve(next_step, isdone, x, i, max_iterations):
    if i > max_iterations or isdone(x):
       return x
    else:
       return recur_improve(next_step, isdone, next_step(x), i + 1, max_iterations)

def improve(next_step, isdone, initval=1, max_iterations=100):
    return recur_improve(next_step, isdone, initval, 1, max_iterations)

def newtons_method(fn, max_iterations=100):
    def newtons_step(x):
        return x - fn(x) / approx_deriv(fn, x)
    def newtons_isdone(x):
        ALLOWED_ERROR_MARGIN = 0.0000001
        return abs(fn(x)) <= ALLOWED_ERROR_MARGIN
    return improve(newtons_step,
                        newtons_isdone,
                        max_iterations)

Then, the recursion can be easily replaced by a while loop :

def improve(next_step, isdone, initval=1, max_iterations=100):
    x = initval
    i = 1
    while i < max_iterations and not isdone(x):
        x = next_step(x)
        i +=1
    return x

Then, one can see that counting iterations is boring. We have builtins to do this in a concise and efficient way.

def improve(next_step, isdone, initval=1, max_iterations=100):
    x = initval
    i = 1
    for i in range(max_iterations):
        if isdone(x):
            break
        x = next_step(x)
    return x

(I might have introduced on off-by-one error in the iteration counts but I can't be bothered).

Then, instead of passing functions using your original functions, you could just write conditions directly :

def improve(fn, initval=1, max_iterations=100, epsilon=0.0000001):
    x = initval
    for i in range(max_iterations):
        if abs(fn(x)) <= epsilon:
            break
        x -= fn(x) / approx_deriv(fn, x)
    return x

Then you don't even need to have multiple functions anymore and your code boils down to :

def newtons_method(fn, initval, max_iterations=100, epsilon=0.00000001):
    x = initval
    for i in range(max_iterations):
        if abs(fn(x)) <= epsilon:
            break
        x -= fn(x) / approx_deriv(fn, x)
    return x

It seems much clearer to me.

Also, your def nth_root(rootfunc, x) function doesn't seem really useful to me. You could just have :

def cuberoot(x):
    return newtons_method(lambda y: y * y * y - x, x)

result = cuberoot(27**3)

print(result)

And get the result you expect.

Finally, your function deserves some documentation.

Final code :

def approx_deriv(fn, x, dx=0.00001):
    """ some docstring. """
    return (fn(x + dx) - fn(x))/dx


def newtons_method(fn, initval, max_iterations=100, epsilon=0.00000001):
    """ some docstring. """
    x = initval
    for i in range(max_iterations):
        if abs(fn(x)) <= epsilon:
            break
        x -= fn(x) / approx_deriv(fn, x)
    return x

def cuberoot(x):
    """ some docstring. """
    return newtons_method(lambda y: y * y * y - x, x)

result = cuberoot(27**3)

print(result)
\$\endgroup\$
1
  • \$\begingroup\$ yes, guess argument is not used. \$\endgroup\$ Commented Apr 20, 2015 at 6:48
0
\$\begingroup\$

As well as the and/or issue I commented on, there's another bug in your code: when newtons_method calls improve, it passes max_iterations as the guess parameter. You should pass it by keyword or supply the guess argument (which you do provide, unused, as a default argument to newtons_method) positionally too.

This demonstrates the importance of proper testing; with only a single test case, an initial guess of 100 still gets to the correct answer within the default 100 steps. I added print(guess) to improve while testing and updating, which would have helped you spot the issue.


I think your derivative approximation will be slightly more accurate if you bracket x:

def approx_deriv(fn, x, dx=0.00001):
    """Approximate derivative of fn at x."""
    return (fn(x + dx) - fn(x - dx)) / (2 * dx)

I have also added a docstring - this is general good practice.


You could factor out the nested function in improve:

def improve(update, isdone, guess=1, max_iterations=100):
    """Improve the guess to a specified accuracy or iteration count."""
    if isdone(guess) or max_iterations == 0:
        return guess
    return improve(update, isdone, update(guess), max_iterations-1)

Note that you don't need an explicit else case where the if block will return.


ALLOWED_ERROR_MARGIN is constant, so I'd declare it at the top level of the script rather than bury it in a nested function. You can use that as the default value, to allow another value to be supplied where necessary (this currently isn't an easy option):

ALLOWED_ERROR_MARGIN = 0.0000001

...

def newtons_method(fn, guess=1, max_iterations=100,
                   margin=ALLOWED_ERROR_MARGIN):
    """Use Newton's method to approximate x for fn(x) == 0."""
    def newtons_update(guess):
        return guess - fn(guess) / approx_deriv(fn, guess)
    def newtons_isdone(guess):
        return abs(fn(guess)) <= margin
    return improve(newtons_update, newtons_isdone,
                   guess, max_iterations)

There is no point to the nth_root function. Surely:

cuberoot(27)

is more readable than:

nth_root(cuberoot, 27)

It's not even a particularly accurate name, as all it does is call the first argument (which doesn't have to be at all related to finding roots) with the second. I would also write y ** 3 rather than y * y * y.


One thing to watch out for is lambda's late binding behaviour (see e.g. Local variables in Python nested functions). If you tried to solve multiple equations at the same time, you might get surprising behaviour. You can solve this with e.g.:

def cuberoot(x):
    """Approximate the cube root of x."""
    return newtons_method(lambda y, x=x: y ** 3 - x)
                                  # ^ note
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.