Chapter VI.  Iteration in Procedural Programming

18. Iterative Loops I:  While

Last revision:  March 23 1997

In this section we introduce iterative loops, the primary method of implementing iteration in procedural programming.  We show how loops are, in some cases, more efficient than list-based or recursive programming.  Finally, we consider the type of evaluation precedence of boolean expressions called "short-circuit evaluation" and discuss its advantages.

Mathematica operations/structures introduced: 
     While[]
     PrimeQ[]
     Prime[]
     short-circuit evaluation

Loops and Efficiency

List-based programming and recursion are two excellent ways to accomplish iteration, because they tend to encourage code which is at once elegant and short.  Still another method for iteration, however, is available:  using iterative loops.  Using such loops produces somewhat longer, less elegant code, but in many situations it is more efficient to use iterative loops, and we introduce it in this section.  Generally, any programming task solvable by list-based programming or recursive programming can be solved by using iterative loops; we have waited to discuss it, therefore, so that the advantages of the first two methods will have become evident before we introduce a method which, while always applicable, may not be the best solution.

The While Construct

The "While[]" construct instructs Mathematica to repeat a sequence of commands, given as the second argument and separated by semicolons if necessary, until the boolean test specified by the first argument becomes False.  In other words, Mathematica first executes the boolean test.  If it is False, the "While[]" command finishes.  If it is True, the "While[]" command executes all of the commands found in the second argument.  Then the boolean test is evaluated again.  If False, the "While[]" command finishes.  If True, the commands are executed again, and so on.  It is important, then, when designing a "While[]" loop---or any loop, for that matter---to insure that at some point the boolean test will result in a False value.  We consider several examples below, comparing list-based to loop solutions.

Example 1:  Finding a Negative; Classic Principles of Loops

How can we find the first negative number in a list of numbers?

List-operation solution

Clear[firstNeg];
firstNeg[x_List] := First[ Select[x, (#<0&)] ]

firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]

This works fine but is inefficient, for it does more work than necessary in determining the entire list of negatives {-7,-2,-1}, from which then selects the first, namely -7.  A more efficient strategy would be to start at the front of the list, working through it until one finds a negative number, and then stopping. This procedure can be accomplished with a "While[]" loop.

While loop solution; Classic Principles

?While

firstNeg[x_List] := Module[{i},
   i = 1;
   While[ x[[i]]>=0, i=i+1 ];
   x[[i]]
]

firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]

Notice that the "While[]" construct executes the commands after the boolean expression repeatedly, checking the value of the boolean expression each time, and stopping when the boolean expression evaluates to False.

Our example contains each of the following classic principles of an iterative loop:

1. We initialize one or more variable(s) before entering the loop.  These variables are typically local.

2. We modify the variable(s) each time through the loop.  In the example above, we increment "i" by 1 every time.

3. After the loop completes, we execute at least one other command to return an answer.  Loop structures themselves have no return value.  In the example above, we execute "x[[i]]" to provide the answer we are seeking.

The boolean expression inside a "While[]" statement will always be False once Mathematica begins to execute the line after the "While[]" statement, if the program ever does exit the "While[]" loop.  Otherwise, Mathematica will enter an infinite loop, which keeps evaluating the same instructions indefinitely, unless you manually interrupt it.  To interrupt a calculation, see "Interrupt Evaluation" under the "Kernel" menu.

While loop solution with error handling

Our "While[]" loop above was not coded to be foolproof.  For instance, what if the value of the parameter is a list with no negative element?

firstNeg[{3,5,2,4,3,11,0,8}]

The first eight entries were non-negative, so it tried the ninth---but there is no ninth element.

What follows is a solution to this relatively common looping problem, that of running beyond the end of a list.  The method below performs correctly because in Mathematica (and many, but not all, other languages) supports short-circuit evaluation: if the first boolean expression in a list of expressions connected by boolean And operations ("&&")  is false, then Mathematica doesn't bother to test the second; if the second is false, it doesn't bother to test the third, and so on.  Consider how short-circuit evaluation is used in the following solution. At the end of the section we will consider short-circuit evaluation in more detail.

Clear[firstNeg];
firstNeg[x_List] := Module[{i},
   i = 1;
   While[ i<=Length[x] && x[[i]]>=0, i=i+1 ];
   If[ i>Length[x], 
     "Sorry, no negative found.", 
     x[[i]] 
   ]
]

In the "While[]" loop above, "i" begins at the value 1 and can reach no higher than one greater than the length of the list "x".  When the "While[]" loop completes, "x[[i]]" is evaluated only if "i" is valid index into the list "x".

firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]

firstNeg[{3,5,2,4,3,11,0,8}]

Recursive solution with error handling

Here is a tail recursive solution.  In this simple example, the recursive solution is as efficient as that with a While loop, and "cleaner" to read.

Clear[firstNeg];
firstNeg[x_List] := 
   Which[
      x == {}, "Sorry, no negative found.",
      First[x] < 0, First[x],
      True, firstNeg[Rest[x]]
   ];

firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]

firstNeg[{3,5,2,4,3,11,0,8}]

Example 2:  Finding the first prime beyond n.

Recall "PrimeQ[]":  a boolean test for a prime number.  Here we use it to find the first prime number beyond "n":

?PrimeQ

firstPrimeBeyond[n_Integer?Positive] := 
   Module[{i},
      i = n+1;
      While[ Not[PrimeQ[i] ], i++];
      i
   ]

firstPrimeBeyond[20]

(Note our use of the increment notation "i++".)  There are two tempting pitfalls to dodge in trying to simplify the code above, as follows:

Pitfall 1:  The While command does not have a return value.

Clear[firstPrimeBeyond];
firstPrimeBeyond[n_Integer?Positive] := 
   Module[{i},
      i = n+1;
      While[ Not[PrimeQ[i]], i++]
   ]

firstPrimeBeyond[20]

The "While[]" loop executed correctly, but provided us with no answer.

Pitfall 2:  Formal parameters cannot be used in place of local variables because formal parameters cannot be modified within a Module.

Many languages allow you to change the value of a formal parameter within the function, treating the formal parameter as a separate local variable, but Mathematica is not one of them.  Therefore we cannot use "n" itself as the variable instead of local "i".

Clear[firstPrimeBeyond];
firstPrimeBeyond[n_Integer?Positive] := 
   Module[{},
      n = n+1;
      While[ Not[PrimeQ[n]], n=n+1];
      n
   ]

firstPrimeBeyond[20]  (* Action, Interrupt this infinite loop. *)

(What happens is that Mathematica substitutes 20 for "n" everywhere in the function, which is a nonstandard procedure.  Thus the first line becomes "20 = 20+1" , generating an error since we can't assign a value to 20.  In most other languages this sort of code would work fine.)

These two pitfalls illustrate why one should generally abide by the three classic principles stated above.

Example 3:  Programming the fixed-point iteration.

Recall that "FixedPoint[]" works like "Nest[]" except that it stops when two consecutive values are recognized as identical.

NestList[Cos, 0.0, 20]

Nest[Cos, 0.0, 20]

FixedPoint[Cos, 0.0]

?FixedPoint

If "FixedPoint[]" was not a pre-defined function, which it is not in many other languages, we could program our own version of "FixedPoint[]", say called "myFixedPoint[]", using a "While[]" loop, as follows.

myFixedPoint[ f_, x0_ ] := Module[ {oldx, newx},
   oldx = x0;
   newx = f[x0];
   While[ oldx != newx,
      oldx = newx;   
      (* replaces oldx with last computed value *)
      newx = f[newx];   
      (* computes a new value *)
   ];
   newx  (* returns answer *)
]

myFixedPoint[Cos, 0.0]

Notice how the second argument of "While[]" may be a compound expression of several lines separated by semicolons, as in a Module.

Example 4:  Listing the prime numbers less than n.

For this example we will use the Mathematica function "Prime[]", which, for a value "i" of the argument, returns the "i"th prime number.  The first 10 prime numbers may then be computed by executing the following expression.

Table[Prime[i],{i,1,10}]

We wish to write a function which will return a list of all of the prime numbers which are less than "n". We can't use "Table[]" since we don't know ahead of time how many there will be, so we use "While[]".

primesUpTo[n_Integer?Positive] :=  
  Module[{i, primeList},
    i = 1;
    primeList = {};
    While[ Prime[i]<n, 
      primeList = Append[primeList, Prime[i]];
      i++
    ];
    primeList
  ]

primesUpTo[30]

primesUpTo[200]

One possible objection to the above program is that it computes "Prime[i]" twice.  This may be inefficient, and it could be disaster in a different problem, if the function we repeated twice returned two different values when executed twice, say for instance if the function computed a random number.  To compute "Prime[i]" only once, we need yet another local variable, in addition to the counter "i" and the cumulative "primeList".

Clear[primesUpTo];
primesUpTo[n_Integer?Positive] :=  
  Module[{i, primeList, nextPrime},
    i = 1;
    nextPrime = Prime[1];
    primeList = {};
    While[ nextPrime < n, 
    		(* update all three variables,in this order! *)
      primeList = Append[primeList, nextPrime];
      i++;
      nextPrime = Prime[i]
   ];
   primeList
]

primesUpTo[200]

Short-Circuit Evaluation

Short-circuit evaluation is a characteristic of a particular sort of "evaluation precedence" which
Mathematica and several other languages support.  Specifically, under short-circuit evaluation, if a sequence of expressions are connected by several instances of "And[]" ("&&") or "Or[]" ("||"), then the sequence of expressions is investigated from left to right, stopping as soon as the ultimate value can be determined.  For instance, if, in an "And[]" construct, an expression evaluates as False, then there is no need to continue, and hence Mathematica will not evaluate any of the remaining expressions in the sequence of expressions connected by "And[]".  Similarly, in an "Or[]" construct, as soon as an expression, looking left to right, has a True value, Mathematica will not evaluate the rest of the expressions, simply returning the value True, since it must be the final value of the sequence of expressions connected by "Or[]".  Here are some examples.

(2==3) && (5==5)

This surely evaluates to False, but Mathematica didn't even check "5==5"!  After "2==3" returned False, it stopped evaluating the "And[]" sequence.  To be sure, let's try this:

Clear[b]
b=2;
(2==3) && ((b=3)==3)

b

Notice that "b" did not become 3, since Mathematica did not evaluate the expression "b=3".  If, however, the first expression evaluated to True, then the second expression would be evaluated.

Clear[b]
b=2;
(2==2) && ((b=3)==3)

b

We have analogous examples for an "Or[]":

Clear[b]
b=2;
(2==2) || ((b=3)==3)

b

Here "b=3" was never evaluated, since the first expression returned True, and hence the "Or[]" must return a True value also.  However, in the following code, "b=3" is evaluated:

Clear[b]
b=2;
(2==3) || ((b=3)==3)

b

To grasp the importance of short-circuit evaluation, consider the following problem.  We wish to check whether or not the reciprocal of an integer is equal to variable "x".  We might try the following statement:

If[(1/i)==x, (* Statement if true *), (* Otherwise *)]

But what if "i" were zero?  Then "1/i" would return an error.  We might then refine our code to be the following:

If[(i!=0)&&((1/i)==x), , ]

In this instance, however, if short-circuit evaluation were not in effect, then "1/i" might be evaluated before "i!=0" was tested, and an error would result.  With short-circuit evaluation, we are guaranteed that the expressions will be evaluated left-to-right and that no error will occur.