Using newthon method to find nth root - did wolframalpha get it wrong?

Question

I'm trying to implement the n-th root algorithm as outlined here:

http://en.wikipedia.org/wiki/Nth_root

My code however, takes a lot of iterations (more than 100) to converge. I tried to check with the wolframalpha:

However, if I look at the steps section, it claims to have done 12 steps to reach the answer:

This seemed very weird and not consistent with the output of my algorithm, so I tried to look at the particular steps:

steps details 2 http://i.snag.gy/AfTAj.jpg

This corresponds with the output of my algorithm, but not at all with the output of the wolframalpha in the previous section!

Or is there something I got wrong? Isn't x12 supposed to be the approximated solution?

My code:

def nth_root(value,n):
    x = Decimal(1.0)
    value = Decimal(value)
    n = Decimal(n)
    for i in range(12):
        print "Step %d" % i
        print "x: %s" % str(x)
        print "residual: %s" % str(pow(x,n) - value)
        print "derivative: %s" % str(n * pow(x, (n-1)))
        print
        print "x%d = %s - (%s)" % (i+1, str(x), str(((pow(x,n) - value) / (n * pow(x,(n-1))))))
        x = x - ((pow(x,n) - value) / (n * pow(x,(n-1))))
        print "x%d = %s" % (i+1, str(x))
        print
        print
    return x

Answer 1

I think (conjecture!) that Wolfram Alpha's algorithm using machine precision is :

• start with the initial value provided $x_0$ and repeat these operations :
• compute the next value $x_{n+1}$ using two methods :
  • the Newton iteration $\;\quad\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}$
  • the alternative iteration $\;x_{n+1}=11\cdot x_n +10$
    (for $x_n$ positive, for $x_n$ negative $\;x_{n+1}=11\cdot x_n -10$).
• the value retained for the next iteration will be the one with the smallest 'residual' $|f(x_{n+1})|$.

To see this method at work simply replace your power of $7$ by $2$ with the following result (Alpha) :

The method used by Alpha is thus not the 'pure' Newton method but a variant with faster convergence.