If it’s worth doing once, it’s worth doing many times

If it’s worth doing once…

It’s worth doing many times

By J. W. Rider

J. W. Rider Consulting

http://www.jwrider.com/

March 2005

“A journey of a thousand miles begins with a single step."
-- Ancient Chinese Proverb

That has got to be one of the best known “getting started” quotations ever. However long and complicated any endeavor might be, it always needs to be initiated with something short and simple. It could also be interpreted to show that no journey ever gets completed that isn’t started. There’s just so many useful ways that you can try to interpret those few words.

Sometimes, the saying is attributed to Confucius. As near as I’ve researched, the saying is more rightfully attributed to Lao-tzu. However, both Confucius and Lao-tzu are misleading. Neither could have ever said it. It would have been just not possible.

How’s that, you ask? Well, there’s an obvious part and a more subtle part. Obviously, the ancient Chinese would not have spoken English. English did not even exist at the time of Lao-tzu.

What’s that? Am I deliberately trying to be an iconoclastic stick-in-the-mud? The saying is just a translation of the original Chinese into English. It happens all the time with famous foreign sayings. Well, I did say there was a more subtle part. If you analyze the saying closely enough, it just might occur to you that the ancient Chinese would not have measured the length of a journey in units invented by the Roman legions as they marched up and down the peninsula of Italia. Whatever the Chinese were thinking, it could not have possibly been anything about miles.

Couldn’t Lao-tzu have been thinking of some ancient Chinese distance? And when it was translated into English, it just happened to convert exactly to a thousand miles? That would have been an incredible coincidence. Please, don’t insult my intelligence, or yours, for that matter.

Fortunately, we don’t have to know exactly what the ancient Chinese were thinking in order to benefit from their proverbs. In fact, there’s a lesson that we can learn even the way that it’s worded at the beginning of the page, with the “thousand mile” business and all.

Let’s get back to the Roman legions for a moment. The length of a mile (from the Latin mille for “one thousand”) was the distance that a Roman legion would travel after taking one thousand paces (or “double steps”). With two steps for every pace, a mile would be the distance traversed after taking two thousand single steps. For a journey of a thousand miles, which must begin with a single step, we would need to take steps as follows:

1,000 miles = 1,000 * 1,000 paces
= 1,000 * 1,000 * 2 steps
= 2,000,000 steps

So, in order to complete a journey of a thousand miles, all you have to do is take two million steps. On the other hand, it also means that if you don’t take two million steps, you cannot possibly complete the journey. Two million steps are two million steps. If you took one step after the other, like you might see in a computer program, you might see something like the following:

TakeSingleStep()

…

This would be continued for two million lines. How big would that be? You can get around fifty lines on a single page. It would take about forty thousand pages. Is that a lot? Well, your average college textbook is only 500 pages. In order to get forty thousand pages, we’d need to buy some eighty college texts. If your college student buys ten texts every semester, eighty texts are what he/she would have at the end of a four-year college curriculum. (Assuming they finish after four years. Assuming they don’t sell the used textbooks back every semester.)

Anyhow, that’s some $6,000 worth of textbooks. I’ve got receipts.

If computer programmers had to work like that, no one would ever take journeys of more than a mile or so. It would just be so expensive to write programs that no one could even afford to buy a computer to run the programs. However, programming languages include some shortcuts that make repeating something two million times as easy as Euler’s number to the pi power. To be sure, there is no magic involved here. In order to go one thousand miles, you do have to take two million steps. Fortunately, you don’t have to write that step in your code two million times.

One thing you can do is write your code with reusable modules. Of course, there is no advantage to this unless you actually reuse the modules. For a thousand-mile journey, we can break the process of stepping two million times into units of various sizes. I would have never considered showing you the forty thousand pages required to write out two million TakeSingleStep() calls, but by dividing the calls up into reusable modules, we can squeeze the whole journey into a couple of pages. I can show you the whole algorithm right here:

PROCEDURE TakeTwoSteps()

BEGIN

TakeSingleStep()

END

PROCEDURE TakeTenSteps()

BEGIN

TakeTwoSteps()

END

PROCEDURE TakeTwentySteps()

BEGIN

TakeTenSteps()

END

PROCEDURE TakeHundredSteps()

BEGIN

TakeTwentySteps()

END

PROCEDURE TakeTwoHundredSteps()

BEGIN

TakeHundredSteps()

END

PROCEDURE TakeThousandSteps()

BEGIN

TakeTwoHundredSteps()

END

PROCEDURE GoOneMile()

BEGIN

TakeThousandSteps()

END

PROCEDURE GoFiveMiles()

BEGIN

GoOneMile()

END

PROCEDURE GoTenMiles()

BEGIN

GoFiveMiles()

END

PROCEDURE GoFiftyMiles()

BEGIN

GoTenMiles()

END

PROCEDURE GoHundredMiles()

BEGIN

GoFiftyMiles()

END

PROCEDURE GoFiveHundredMiles()

BEGIN

GoHundredMiles()

END

PROCEDURE GoThousandMiles()

BEGIN

GoFiveHundredMiles()

END

On the surface, it might look like we only execute TakeSingleStep() twice. However, if you analyze the pseudocode carefully, you’ll quickly realize that if GoThousandMiles() is called, then TakeSingleStep() will indeed be executed two million times. $6000 worth of college texts have been reduced down to thirty cents. Definitely, a bargain.

We can do even better using iteration. Just take all the redundant statements and roll them up into a loop construct, as follows:

FOR I=1 TO 2000000

TakeSingleStep()

And in one fell swoop, we’ve reduced the number of lines of source code required from two million down to only two. If only it were as easy to reduce the cost of four years worth of college textbooks down to a mere fraction of a cent. We cannot always expect cost reductions like that, but it does give us a hint of just how lucrative being able to represent repetition by iteration within computer programs is.

Something to remember in the previous example is that the step TakeSingleStep() still needs to be executed two million times. There’s nothing magical about the FOR loop. The only way to traverse a distance of a thousand miles is to make two million steps.

Of course, it does help if we knew exactly how many steps we would make before we start programming. The FOR loop captures that conditions. We would use a WHILE loop to capture the condition that we want to keep taking single steps until we arrive at the end of the journey.

WHILE Ask(“Are we there yet?”)=“No”

TakeSingleStep()

Whether we know the explicit number ahead of time, or we stop stepping at the destination, we still need to take two million steps. No matter how we organize the steps, we still need to take that many. For instance, we could use a nested iteration with two loops. The outer loop counts each mile; the inner loop counts the number of steps within a single mile. Eventually, TakeSingleStep() will be executed two million times and the journey completed.

FOR MILE=1 TO 1000 … a journey of 1,000 miles is done

… one mile at a time.

FOR STEP=1 TO 2000 … 2,000 standard Roman legionnaire

… steps in a single mile

TakeSingleStep()

Of course, as I mentioned at the beginning of the page, the ancient Chinese probably did not have in mind a journey of exactly one thousand miles. We can generalize the code, and make it useful in more than one program by passing the length of the journey as an argument to the routine.

PROCEDURE JOURNEY(NumberOfMiles) … iterative form

FOR MILE=1 TO NumberOfMiles … one mile at a time

FOR STEP=1 TO 2000 … Two thousand steps per mile.

TakeSingleStep()

END

This still does not change the number of times that TakeSingleStep() must be performed. If we make a journey of one thousand miles, TakeSingleStep() gets executed two million times.

In the previous examples, all the ways we were exhibiting for completing a journey were examples of iteration. Iteration works by executing a small piece of the program multiple times until a given task is completed. If you want to slice salami by iteration, you cut off a small slice, then another small slice, then another small slice, until there is no more salami left.

Another approach for accomplishing the same thing is called recursion. Recursion works by dividing the task into a more or less equal number of parts and then dividing each of those parts into another more or less equal number of parts, until each part performed without partitioning. To slice salami by recursion, cut the salami in half. Then cut each half into quarters. Each quarter into eighths. Until the large pieces are smaller than a single slice.

To take journey of a thousand miles recursively, we first take a journey of five hundred files and then take a second journey of five hundred miles. We keep dividing the journey into shorter lengths until the journey is so short that we just take a single step. Something like the following:

PROCEDURE JOURNEY(NumberOfMiles) … recursive form

IF NumberOfMiles<=1/2000 THEN … short journeys only take

TakeSingleStep() … a single step

ELSE BEGIN … otherwise

CALL JOURNEY(NumberOfMiles/2) … divide the journey

… into two halves

CALL JOURNEY(NumberOfMiles/2) … and solve each

… separately

END

Just as in the case of iteration, we still execute TakeSingleStep() two million times. The only difference is how the statements get organized.