Copyright (C) 1997 Rich Neidinger, John Swallow, and Todd Will.  Free for
distribution to college and university instructors for personal,
non-commercial use.  If these notebooks are used in a course, the authors
request $20 per student.

Chapter VI.  Iteration in Procedural Programming

18. Iterative Loops I:  While

Last revision:  September 25 1996

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.

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 Calculation" under the "Action" 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}]

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.