4 ms·
If you use a termination condition that has to do with convergence of iterates instead of a number of iterations (often the case), then you generally don't know
by gugagore 6y ago
If you use a termination condition that has to do with convergence of iterates instead of a number of iterations (often the case), then you generally don't know beforehand the length of the finite sequences. Maybe you know a bound, but in general you might not even have that.
In an important sense, it only becomes a finite algorithm. It isn't one. You cannot write the finite sequence of instructions down. It's got loops.
To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers.
- yakubin 6y ago> To your point about approximations vs not, if you have an algorithm that, for any desired approximation accuracy can compute the square root to that accuracy in a finite number of steps, then that process is as much "the square root" as anything involving the real numbers. Not really, since approximations, no matter how accurate, don't preserve algebraic properties. You only get to know what it's bigger/smaller than.
- gugagore 6y agoI think I understand what you mean, so let me dial back "anything involving the real numbers". If you are representing or thinking of "sqrt(2)" as "the positive solution to x^2 = 2", then you preserve algebraic properties. But you generally (correct me if I'm wrong) don't get to know whether it's bigger or smaller than something else of the form "the _choose_uniquely_ solution to _some_equation_" unless you rely on an argument where you invoke approximations.