Iteration: Approaching an Answer Step by Step

Iteration means repeating one rule, with each pass starting from where the last pass finished. Two kinds matter. A fixed count repeats a stated number of times: the Nakshatra ladder runs twelve months and stops. A search repeats until a condition is met: bisection halves a bracket around the rate that reaches Rs 120/-, and ten steps shrink that bracket to one thousand and twenty fourth of its starting width.

Every rate, every reading and every bracket width below is the output of one arithmetic rule, and the rule is short enough to print in a line: begin at Rs 100/-, multiply by one plus the monthly rate, take Rs 2/- off, and do that twelve times. A calculator and some patience rebuild all twenty two steps and land on the same digits. Nothing in the sequence has to be taken on trust.

The Nakshatra ladder has already appeared. The ladder, an invented arithmetic rule, runs like this: start at Rs 100/-, multiply by one plus a monthly rate, subtract a standing chargeA fixed amount taken off every month whatever else happened, which here is the Rs 2/- the rule subtracts before the next month begins. of Rs 2/-, and repeat that twelve times. Two things about the ladder are already settled. At a rate of exactly 2.00 per cent a month the ladder sits flat at Rs 100.0000/- for all twelve months, and that case has a closed formAn answer that can be written down as a finished expression and worked out in a single pass, with no repeating involved. Here it is one division.: the charge over the starting figure, Rs 2/- over Rs 100/-, and no arithmetic beyond that division. At a target of Rs 120/- there is no such expression at all. The rule cannot be rearranged to hand over the rate, and no amount of algebra changes that.

Which leaves the only option that remains: try a rate, look at what the ladder reads, and try again somewhere better. Trying has a shape. A rule repeated so that each pass builds on the last can be organised to close in rather than wander, and it can be told when to stop. None of that needs anything but arithmetic and a willingness to do it several times over.

Before any of that, the everyday version. Ten shops in one mall have rents that go up by ten per cent every year. A shop paying Rs 20,000/- a month this year pays Rs 22,000/- next year, then Rs 24,200/-, then Rs 26,620/-. After eleven of those raises it pays Rs 57,062.33/-, and that figure does not depend on the first year except through the ten years in between. Each year's answer is the next year's starting point. Every shopkeeper in that mall runs an iteration in their head without ever needing a word for it.

What is iteration, and how is it different from doing something twice?

Iteration is repeating one rule where each pass starts from where the last pass finished. The second half of that sentence is the whole of it. Doing the same thing several times over is repetition, and repetition hands back several answers to the same question. The passes of an iteration are joined end to end rather than run side by side, so iteration hands back one answer that has moved. The joining is exactly why an iteration can travel somewhere. A repetition can only stand where it started and say the same thing again.

A rent rise put through both arrangements makes the difference concrete. A ten per cent rise applied to Rs 20,000/- four separate times gives Rs 22,000/- four times over. Four copies of one fact. Applied four times in a chain, each rise landing on whatever the last one produced, it gives Rs 22,000/-, then Rs 24,200/-, then Rs 26,620/-, then Rs 29,282/-. Same rule, same number of applications, and the second arrangement has reached somewhere the first cannot get to however many times it is run.

The joining charges something as well as buying something, and the charge is worth naming now because these notes on method keep walking into it. Because every pass carries the last one forward, whatever went wrong on pass three is still sitting inside pass four. A repetition that goes wrong once is wrong once and no more. An iteration that goes wrong once may carry that wrongness all the way to the end, and whether the damage fades or grows as it travels is a separate question with its own notes.

What are the two kinds, and which single question tells them apart?

One question separates them, and it can be asked before writing a single line of arithmetic. Is the number of passes known in advance?

If the answer is yes, the arrangement is a fixed count. Twelve months is the question being asked, so the Nakshatra ladder run over twelve months is a fixed count. Twelve passes is what the rule gets, and it would still be twelve if the readings came out at Rs 40/- or at Rs 400/-. The count was never in the arithmetic's hands. Nothing the readings produce along the way can lengthen it or cut it short.

If the answer is no, the arrangement is a search. Bisection on the Rs 120/- target is a search. The run repeats until the two ends it is working between are close enough together, and how many passes that takes depends entirely on how close was demanded. Ten steps satisfies one demand and twenty two satisfies another, and neither number was known before the run began.

A fixed count states its count before it starts, so a fixed count always finishes. A search finishes only if the condition it is waiting for can be reached at all. The gap between the two is not a small difference in temperament, but the difference between a run that has an end and a run that has a hope of one. Every serious failure described below grows out of it, and so does the reason a search always needs a cap on how many passes it may take before it gives up and says so.

How does bisection actually work, step by step?

Bisection needs one thing before it starts: a pair of rates the answer is confidently taken to sit between. Given that, the whole method is three lines, and they repeat until something stops them.

The only operation anywhere in those three lines is a comparison: is this reading below the target or above it. No slope, no rate of change, no clever guess at where the answer might be hiding, and no assumption about the shape of the rule beyond one. The plainness is not a limitation dressed up as a virtue. Nothing in bisection is sophisticated enough to be wrong about, and a method with nothing to be wrong about cannot fail in the ways cleverer methods fail.

The one condition line three needs is worth saying out loud. The rule's reading has to move in a single direction as the rate rises, and this one does: the ladder reads Rs 87.3175/- when the monthly rate is 1.00 per cent, then Rs 100.0000/- at 2.00, Rs 114.1920/- at 3.00, Rs 130.0516/- at 4.00, and Rs 167.4798/- once the rate reaches 6.00. A rule that behaves that way is monotoneMoving in one direction throughout and never turning back, so a higher input always gives a higher reading., and on a monotone rule a reading above the target really does mean that every rate above that middle value reads above the target too. Throwing half away is therefore safe rather than merely convenient.

One more property is worth noticing while the method is this simple. Bisection is deterministicProducing the same output every time from the same starting point, with nothing random anywhere in it.. Give it the same two ends and the same rule and it produces the same middle values in the same order, on any machine, on any afternoon. No drawn number enters bisection anywhere, so there is no starting value for a stream of drawn numbers to name. Seeding such a stream is covered under computer randomness, and bisection does not need it.

What does the whole search look like on the Rs 120/- target?

Start with a bracket of 2.00 to 6.00 per cent a month. The pair is a legitimate starting point for the Rs 120/- target for exactly one reason: the ladder reads Rs 100.0000/- at the lower end and Rs 167.4798/- at the upper, so the target sits between the two readings. A pair of ends earns the right to be called a bracket by having the target fall between what they read, never by looking wide enough to be safe. That distinction costs one minute at the start and it is the check most searches are missing.

Here are the first ten steps in full. Each row shows the two ends going in, the middle value tested, what the ladder reads there, and which half survived the comparison.

Every step halves the width, and it does so without consulting the readings at all. Four percentage pointsThe plain gap between two per cent figures, so 3.38 per cent less 3.37 per cent is one hundredth of a percentage point. becomes two, then one, then half of one, and so on down. After those ten steps the two ends run from 3.378906 to 3.382812 per cent. The width is 0.00390625 of a percentage point, one thousand and twenty fourth of the width it began with. Ten comparisons bought a thousandfold narrowing, and not one of them required knowing anything about the rule except whether a reading came in high or low.

Keep going and the narrowing keeps its pace. By the twenty second step the middle being tested is 3.379155 per cent, where the ladder reads Rs 119.999995/-, and the two ends run from 3.379155159 to 3.379156113 per cent. The width is then roughly one part in 41,94,304 of where the search started. Twenty two doublings of precision look like that written out.

A search that hands back a number has proved nothing at all. The returned answer goes back through the original rule first. Carried to nine decimal places of a per cent the answer is 3.379155475, and the ladder run at that rate reads Rs 120.000000/- to six decimal places and past them. Carried to six decimal places instead, 3.379155, the ladder reads Rs 119.999993/-, short of the target by about seven millionths of a rupee. Both figures are perfectly fine to print. Only one of them is fine to put back into the rule and call an exact hit, and knowing which is which is the whole of what the precision of a returned answer means.

There is a second check and it costs even less. Point the same procedure at the case whose answer is already known. Bisection on the Rs 100/- target, from a starting bracket of 1.00 to 4.00 per cent, returns 2.000000 per cent. The closed form for the flat case says the rate is the charge over the starting figure, Rs 2/- over Rs 100/-, or 2.00 per cent exactly. The two agree to fifteen decimal places. A method that gets the known case right has earned the right to be pointed at the case nobody can check, and a method that gets it wrong has said so before costing anything.

What can a bracket promise that an estimate cannot?

At every one of those twenty two steps the run could have stopped and said something exact. The answer is between these two numbers. Not probably, not within a margin, not nineteen times out of twenty. Between these two numbers, and that is the end of the sentence.

One other way of getting a number out of a rule that cannot be solved stands beside bisection: draw a great many random cases, work each one through and report what came back. An estimate built that way arrives with a standard errorThe typical distance between an estimate built from a limited number of draws and the quantity it is estimating. Earlier notes build it in full. attached, and what a standard error buys is a statement of the form the answer is probably within so much of this. Probably. A pair of bisection ends is a different kind of sentence altogether: it says the answer is definitely inside this range, and on most problems that difference is worth a great deal more than speed.

Watch what the answer never does across the whole run. The answer never leaves. After step one it is inside 2.000000 to 4.000000 per cent. After step ten it is inside 3.378906 to 3.382812. After step twenty two it is inside 3.379155159 to 3.379156113. Every one of those statements was exact when it was made, none of them was ever revised, and each one is simply a tighter version of the one before rather than a correction of it.

The reason it never leaves is the comparison at line three, and it is worth seeing why rather than taking it on trust. On a monotone rule every rate in the discarded half reads on the wrong side of the target, so the half being thrown away is the half that cannot contain the answer. Nothing is being estimated when that half goes. The half is being ruled out. A method that only ever discards what it has already checked keeps the answer between its two ends from the first step to the last, and that, rather than any question of speed, is the whole of what bisection promises.

Choosing a tolerance depends on what the answer is for. How narrow is narrow enough is settled under convergence and tolerance, and so is the comparison between the speed of this narrowing and the speed of a simulated estimate. The promise itself has one shape: certainty about a range, bought with comparisons, one factor of two at a time.

When should the repeating stop, and which rule is wrong?

By definition nobody told a search how many passes to run, so a search has to be told when to stop. Three stopping rules are in common use. Two of them are defensible and one is wrong.

The first is to stop when the two ends are close enough together. The gap between the ends is a real statement about where the answer is rather than a hint about it, so on bisection stopping on the width is the honest rule. When it is small, what is known is correspondingly narrow.

The second is to stop when the reading is close enough to the target. The gap between the current reading and the target has a name, the residualThe distance between where a reading currently stands and the target it is chasing, measured in whatever units the reading uses., and this rule watches that instead of watching the rate. The residual is the right thing to watch whenever what matters is the consequence of the answer rather than the answer itself. On the ladder that means the rupees rather than the rate.

The third is to stop when the step gets small, and that is the wrong one, for a reason that does not show up on this problem at all: a small step means the method is moving slowly, not that it has arrived. Those two sound like the same thing and are not, and telling them apart is the difference between a search that can be trusted on a new problem and one that cannot.

On the ladder the two happen to coincide, and the coincidence is precisely what makes the fault hard to see. Nudge the rate by a millionth of a whole unit and the ladder's reading at the end of its twelve months shifts by Rs 0.001564/-, so by the time the steps are that small the readings really have gone still, and a search stopping on step size lands somewhere sensible. The agreement is a fact about how gently this particular rule responds, not a fact about the stopping rule. Draw a rule ten times as steep through the same point and the same step of one in a million moves the reading by Rs 0.015642/-. A hundred times as steep and it is Rs 0.156421/-. More than fifteen paise of error hides behind a step that looked reassuringly tiny. The method halves whatever problem it is pointed at, so the step size is a fact about the method. The residual is a fact about the problem. Only the residual needed to be made small.

How is it known that the repeating will finish at all?

For a fixed count the question barely exists. A fixed count finishes for one reason only: the count was stated. The only way it fails to finish is if somebody forgot to state one.

For bisection the answer is almost as firm, and it comes from the halving rather than from the rule being searched. The width after any number of steps is four percentage points divided by two raised to that number of steps, and that is a complete description with no readings in it. Any named width is reached in a countable number of steps: one in a million of a whole unit of the rate takes sixteen steps and one in a hundred million takes twenty two. The halving never consults a reading before halving, so no shape of rule and no unlucky run can stretch those counts.

One case still remains: the condition itself is out of reach, and here the cap earns its keep. The only alternative to stopping is running forever, so a search written without a stated maximum number of passes is a defect rather than a matter of style. Ask for a residual below one ten thousandth of a paisa on a rule whose arithmetic cannot carry that many digits and the condition will never be met, however patient the machine is. With a cap, the run ends and says it did not converge, and a failure announced is information. Without a cap the run simply never comes back, and silence is not.

The commonest reason a condition turns out to be unreachable is a bracket that never contained the answer in the first place. Hand the same procedure a starting pair of 4.00 to 6.00 per cent for the Rs 120/- target. The ladder reads Rs 130.0516/- at one end and Rs 167.4798/- at the other, and the target sits below both of them. Every middle it tests reads above the target, so the upper half is discarded every single time and the pair marches steadily down onto its own lower end: 5.000000 per cent reads Rs 147.7514/-, then 4.500000 reads Rs 138.6601/-, then 4.250000 reads Rs 134.2970/-, and it goes on shrinking towards 4.000000 per cent forever. A search stopping on the residual will never get there and the cap will fire, and the firing is the warning working. A search stopping on the width will stop cleanly and report 4.000000 per cent, whose reading is Rs 130.0516/-, a full Rs 10.0516/- from what was asked for, with nothing in the run to say so. Only putting the answer back through the rule catches that one.

What does an analyst check before trusting a returned answer?

Iteration is where a great deal of everyday quantitative work actually happens, and almost none of it looks dramatic. Someone in a lending team backs out the rate implied by a schedule of payments. Someone in a valuation team backs out the growth figure that makes a set of assumptions land on a stated total. A household working out what monthly saving reaches a school fee in six years is doing the identical thing on a smaller sheet: guess, run it forward, look at the gap, guess again. In every one of those, a number comes back out of a repeating procedure, and the person receiving it has to decide whether to build anything on it.

Three checks decide that, and together they take about a minute.

Check one, and it costs a single line: put the returned answer back into the original rule and see whether it produces the target. Take 3.379155475 per cent, run twelve months of the ladder, and read Rs 120.000000/-. Almost every fault a search can suffer ends with a number that does not satisfy the thing it was supposed to satisfy, so this one check catches almost everything a search can get wrong. A search that stopped too early fails it. A search that ran on a bracket that never held the answer fails it. A search whose stopping rule was watching the wrong quantity fails it. A returned number that has not been put back through the rule is a claim, not a result.

Check two is about where the search began rather than where it ended. Confirm that the two starting ends really did sit on opposite sides of the target, by reading the rule at both of them. At 2.00 per cent the ladder gives Rs 100.0000/-, at 6.00 per cent it gives Rs 167.4798/-, and the target of Rs 120/- sits between the two. The straddle check would have caught the 4.00 to 6.00 pair before a single step ran, and it costs two runs of the rule.

Check three is about the method rather than the run. The same procedure is pointed at a case whose answer is already known, to see whether it comes back with the right thing. Bisection on the Rs 100/- target returns 2.000000 per cent, and the closed form says exactly 2.00 per cent. The known case is a small ceremony, and it has caught reversed comparisons, wrong targets and off by one loops in more places than anybody enjoys admitting.