19. Iterative Loops II:  Do, For

Last revision:  March 19 1998

In this section we continue our consideration of iterative loops, introducing the "Do[]" and "For[]" variants of the "While[]" loop.  These variants provide structured ways to accomplish common looping operations.

Mathematica operations/structures introduced: 
     Do[]
     For[]

Examples of Basic Looping Techniques

We first present two more examples of "While[]" loops and discuss each of them.   It is especially important in the loops below to understand what variables are updated with every iteration of the loop and the way in which this updated variable affects the operation of the boolean test which controls exit from the "While[]" loop.

Harmonic series

In theory, the sum of the Harmonic Series 1/1 + 1/2 + 1/3 + 1/4 + ... grows arbitrarily large.  (This is not as obvious as you might think since 1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + ... sums to a finite number!)  Below we consider a function "whenSumBeat[goal]" that counts how many terms of the harmonic series are necessary for the series to surpass a given number.  In other words, "whenSumBeat[goal]" will return the first "n" such that 1/1 + 1/2 + 1/3 + ... + 1/n  is greater than "goal".

Clear[whenSumBeat]
whenSumBeat[goal_?NumberQ] := Module[ {sum, n},
   sum = 0;
   n = 0;
   While[ sum <= goal,
      n++;
      sum = sum + 1/n
   ];
   n
]

whenSumBeat[5]

whenSumBeat[8]

Notice that two variables are initialized before the loop begins.  One, "sum", is initialized to zero and will hold the value of the sums we will be computing, namely, 1/1 + 1/2 + ....  The other, "n", is initialized to zero and will represent the denominator of the term we will add to "sum".  The variable "n" is initialized to zero because the first command of the loop is to increment the value of "n" before adding "1/n" to "sum"; thus "n" must begin at zero so that "1/1" is the first fraction added to "sum".  Also take note of the fact that this loop must execute two commands, one to increment "n", the other to add "1/n" to "sum".  While "n" holds the value in which we are ultimately interested, "sum" must be continually computed so that we can have an appropriate boolean test to control execution of the loop.

Powers of 2

Here we consider a similar function, "whenPowBeat[goal]", which will return the first nonnegative value of "n" such that 2n > "goal".  We could solve this problem with logarithms or by using the ^ operation.  We do neither; instead, we will accumulate a product by multiplying by 2 each time through the loop until the product exceeds the goal.  The answer will be a count of how many times the loop body was executed.  (In the previous example, "n" was the loop counter.)

Clear[whenPowBeat]
whenPowBeat[goal_?NumberQ] := 
  Module[ {product, counter},
    product = 1;
    counter = 0;
    While[ product <= goal,
      counter++;
      product*=2
    ];
    counter
  ]

Notice that two variables are initialized before the loop begins.  One, "product", is initialized to one and will hold the value of the products we will be computing, namely, 2*2*2*....  The other, "counter", is initialized to zero and will represent the number of 2's we have placed in the product.  The variable "counter" is initialized to zero because the loop counts how many 2's are already in the product, and, at the beginning, the product contains no 2's.  Also take note of the fact that this loop must execute two commands, one to increment "counter", the other to multiply "product" by 2.  While "counter" holds the value in which we are ultimately interested, "product" must be continually computed so that we can have an appropriate boolean test to control execution of the loop.

In general, deciding how to initialize the variables which are updated in a loop can be a tricky matter.  One way to help determine whether or not the initializations may be correct is to consider the cases in which the loop does not execute (in which case the boolean test returns False on its first evaluation) and in which the loop executes exactly once.  In our case above, "counter" should remain 0 if "goal" is less than 1, for we will need no 2's at all.  Similarly, "counter" should stop at 1 if "goal" is between 1 and 2, for we will need exactly one 2 in "product".  We check these to cases in the following commands:

whenPowBeat[.5]

whenPowBeat[1.5]

Since these work, we have some confidence that "counter" and "product" are initialized correctly.

whenPowBeat[10000]

Do

When we do not know how many times a function or an operation should be performed, the strategy of using list-based functions to accomplish the task may not be appropriate, since most such functions operate only on entire lists.  Instead, we should employ recursion, or a "While[]" loop.  When we do know how many times an operation should be performed, however, we could use the old list-based functions such as "Table[]", "Fold[]", and "Nest[]".  However, these operations can be inefficient at times, as we saw in the previous section, and, moreover, many languages do not have analogues of such operations.  Typically other languages do have companions to the standard "While[]" construct, called the "Do[]" and "For[]" constructs, which provide ways to iterate a process a fixed number of times.

The syntax for a "Do[]" construct is simple: the first argument is a sequence of statements (separated by semicolons); the second argument is an iterator.  "Do[]" constructs are very similar, then, to instances of "Table[]".  We use and compare both in the following examples.

Finding the sum of squares of even numbers

Here we try to find the sum of the squares of the even numbers between 1000 and 2000.

List-based solution

Apply[Plus,Table[i^2,{i,1000,2000,2}]]

Do loop solution

Module[ {sum,i},
   sum = 0;
   Do[sum = sum + i^2, {i,1000,2000,2}];
   sum
]

Note that "Do[]" constructs have no return value, so we must still execute "sum" in the Do-loop solution above in order to write out the value.  Is there any advantage to the iterative solution?  Yes: using "Table[]" at least temporarily tied up the computer's memory with a list of 501 integers, while the Do loop kept only one integer in memory, "sum" (in addition to the control variable "i"), during its execution.  On a 386 PC computer, when one runs the list solution with 2000 changed to 2 million, the computer starts frantically flashing the hard-disk light as it tries to find room to record all of the list.  The Do loop solution, on the other hand, does not cause any memory problems, although it does take an equally long time.  (While other computers may be faster and have more memory, there will be a number large enough to cause the memory problems with the list-based solution!)

In defense of list-based thinking, however, we point out that Mathematica does provide the function "Sum[]"; here is the best Mathematica solution.

Sum[i^2,{i,1000,2000,2}]

One could consider the functions "Nest[]", "FixedPoint[]", "Sum[]" and "Product[]" in the category of list-based programming, but actually they are not manipulating lists!  They are special cases of iteration loops that are built into the language.  Thus, "Sum[]" is really a basic Do loop in disguise.  We have errantly called "Sum[]" a list-based function because we have considered it as a single operation.

Fibonacci numbers with Do

Read the following function and decipher its action.

Clear[fib];
fib[n_Integer?Positive] := Module[{oldfib,newfib,newestfib},
   oldfib = 1;
   newfib = 1;
   newestfib = 2;
   Do[
      oldfib = newfib;
      newfib = newestfib;
      newestfib = oldfib + newfib
   ,{n-3}];
   If[n<=2, 1, newestfib]
]

Map[fib,Range[5]]

fib[300]

This function "fib[]" is much more efficient than a recursive version which does not implement dynamic programming. This solution is similar to a recursive version which does employ dynamic programming, but it is slightly faster since it does not need to keep track of many function calls, remembering parameters and return values from many executions of the same function over and over again.  The loop simply keeps track of three integers.  Let's time the various versions to convince ourselves.

Timing[fib[26]]

Clear[fib2]
fib2[1]=1;
fib2[2]=1;
fib2[n_]:=fib2[n-1]+fib2[n-2];
Timing[fib2[26]]

Clear[fib3]
fib3[1]=1;
fib3[2]=1;
fib3[n_]:= fib3[n] = fib3[n-1]+fib3[n-2];
Timing[fib3[26]]

For

A "For[]" construct encapsulates in one structure the idea of a loop in which (a) initialization occurs before the loop begins; (b) an operation, usually that of incrementing a variable, occurs at the end of every iteration; and (c) the loop stops when a certain boolean function returns False.  Thus, a For loop combines the versatility of a "While[]" construct (with the boolean test) with a distinguished place to write the instructions for the end-of-iteration operation.  Many languages support an analogue of the "For[]" construct.

The syntax of a "For[]" construct is as follows.  "For[]" takes four arguments, separated by commas as usual, and each argument can be a list of expressions separated by semicolons.  The first argument contains code which will be executed before the loop starts (the initialization);  the second contains the boolean test, which will be tested before each iteration begins and which controls whether or not the loop will continue executing; the third, the update operation (usually incrementing a test variable); and the fourth, the actual body of the loop.  We'll consider the above examples written with a "For[]" construct instead.

Harmonic series

Clear[whenSumBeat]
whenSumBeat[goal_?NumberQ] := Module[ {sum, n},
   For[sum=0; n=0, sum<=goal, n++, sum+=1/n];
   n-1
]

Initialization:  "sum" is set to 0, "n" to 1 (why is "n" initialized differently than it is in the previous version, and why is "n-1" returned instead of "n"?).
Boolean test:  we wish to iterate if "sum<=goal" before the iteration.
End-of-iteration operation:  "n++" increments "n" by 1.
Body:  "sum" has "1/n" added to it.

Powers of 2

Clear[whenPowBeat]
whenPowBeat[goal_?NumberQ] := 
  Module[ {product, counter},
				For[ product=1; counter=0, product<=goal,     
									product*=2, counter++];
    counter
  ]

Initialization:  "product" is set to 1, "counter" to 0.
Boolean test:  we wish to iterate if "product<=goal" before the iteration.
End-of-iteration operation:  "product" is doubled.
Body:  "counter" is incremented by 1.

Finding the sum of squares of even numbers

Module[ {sum,i},
   For[sum=0; i=1000, i<=2000, i+=2, sum+=i^2];
   sum
]

Initialization:  "sum" is set to 0, "i" to 1000.
Boolean test:  we wish to iterate if "i<=2000" before the iteration.
End-of-iteration operation:  "i+=2" increments "i" by 2.
Body:  "sum" has "i^2" added to it.

Fibonacci numbers with For

Clear[fib];
fib[n_Integer?Positive] := Module[{oldfib,newfib,newestfib,i},
  For[oldfib=newfib=newestfib=i=1,
  			i<=n-2, i++,
  			oldfib = newfib;
  			newfib = newestfib;
  			newestfib = oldfib + newfib];
  newestfib
]

Initialization:  "oldfib", "newfib", "newestfib", and "i" are all set to 1.
Boolean test:  we wish to iterate if "i<=(n-2)" before the iteration would start.
End-of-iteration operation:  "i++" increments "i" by 1.
Body:  "oldfib" becomes what "newfib" was; "newfib" becomes what "newestfib" was, and "newestfib" becomes the sum of those two quantities.

Notes

Note that the end-of-iteration operation can always be omitted from its proper place and simply placed at the end of the body, where it will be executed with each iteration.

Note that a While loop "While[test, body]" corresponds exactly to "For[ , test, , body]".

Note that a Do loop "Do[body, {x,xmin,xmax,xinc}]" corresponds exactly to "For[x=xmin, x<=xmax, x+=inc, body]".