# Cell seems to be evaluating in exponential time even though it shouldn't

I am trying to implement Newton's method for a given function f[x] and a starting x-value xval. The code should print out each new x-value as it approaches one of the zeroes of the functions. g[x] is a function that returns the new x-value given an old x-value.

f[x_] = x^3 - x;
g[x_] = x - (f[x]/D[f[x], x]);
zeroes = (x /. Solve[f[x] == 0, x]);
xval = 1000;
shouldStop = False;
While[Not[shouldStop], distances = g[xval] - zeroes;
results = Map[Less[Abs[#], 0.00001] &, Abs[distances]];
xval = g[xval]; Print[N[xval]]; shouldStop = Or @@ results]


I am not sure why, but as the while loop continues, each iteration takes longer to run. Any help?

-
It's because you are using exact arithmetic (a simple Print[distances] would have shown this. You can address this by changing the initial value to xval=1000,;. – Daniel Lichtblau Feb 27 '14 at 17:07
@DanielLichtblau Might merit an answer, because more users are bound to encounter them exact arithmetic things :D – Yves Klett Feb 27 '14 at 17:19
@DanielLichtblau Thanks that makes sense now. I changed it to xval = 1000//N; and it works! – Adam S Feb 27 '14 at 17:52

(1) Use Print, say, to see what exactly is happening under the hood. Something like the code below would have given a strong indication of what was happening.

j = 0;
While[Not[shouldStop] && j <= 5,
j++;
distances = g[xval] - zeroes;
results = Map[Less[Abs[#], 0.00001] &, Abs[distances]];
xval = g[xval];
Print[N[xval]];
Print[results];
shouldStop = Or @@ results]


(2) With the problem now understood, (exact arithmetic giving fractions with ever larger parts), one can avoid it by working with numeric arithmetic. A simple way to accomplish this would be to give an approximate number for start value, e.g. xval=1000.;.

(3) Once you ascertain that speed is now as expected, you can remove the j<=5 restriction.

I will remark that the complexity increase is pretty much quadratic per iteration. This means it is exponential in the number of iterations, but quadratic in the size of residual (since that also decreases quadratically, at least when we get within the Newton attraction region).

-