(*^
::[ Information =
"This is a Mathematica Notebook file. It contains ASCII text, and can be
transferred by email, ftp, or other text-file transfer utility. It should
be read or edited using a copy of Mathematica or MathReader. If you
received this as email, use your mail application or copy/paste to save
everything from the line containing (*^ down to the line containing ^*)
into a plain text file. On some systems you may have to give the file a
name ending with ".ma" to allow Mathematica to recognize it as a Notebook.
The line below identifies what version of Mathematica created this file,
but it can be opened using any other version as well.";
FrontEndVersion = "Macintosh Mathematica Notebook Front End Version 2.2";
MacintoshStandardFontEncoding;
fontset = title, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e8, 24, "Times";
fontset = subtitle, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeTitle, center, M7, bold, e6, 18, "Times";
fontset = subsubtitle, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeTitle, center, M7, italic, e6, 14, "Times";
fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect,
groupLikeSection, grayBox, M22, bold, a20, 18, "Times";
fontset = subsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, blackBox, M19, bold, a15, 14, "Times";
fontset = subsubsection, inactive, noPageBreakBelow, nohscroll,
preserveAspect, groupLikeSection, whiteBox, M18, bold, a12, 12, "Times";
fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
12, "Times";
fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 10, "Times";
fontset = input, noPageBreakInGroup, preserveAspect, groupLikeInput, M42,
N23, bold, B65535, L-5, 12, "Courier";
fontset = output, output, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = message, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, R65535, L-5, 12, "Courier";
fontset = print, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, L-5, 12, "Courier";
fontset = info, inactive, noPageBreakInGroup, preserveAspect,
groupLikeOutput, M42, N23, B65535, L-5, 12, "Courier";
fontset = postscript, PostScript, formatAsPostScript, output, inactive,
noPageBreakInGroup, preserveAspect, groupLikeGraphics, M7, l34, w282, h287,
12, "Courier";
fontset = name, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
italic, 10, "Geneva";
fontset = header, inactive, noKeepOnOnePage, preserveAspect, M7, 12, "Times";
fontset = leftheader, inactive, L2, 12, "Times";
fontset = footer, inactive, noKeepOnOnePage, preserveAspect, center, M7,
12, "Times";
fontset = leftfooter, inactive, L2, 12, "Times";
fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7,
10, "Times";
fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = completions, inactive, nohscroll, noKeepOnOnePage,
preserveAspect, M7, 12, "Times";
fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect,
M7, 12, "Times";
currentKernel;
]
:[font = smalltext; inactive; preserveAspect]
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.
:[font = title; inactive; preserveAspect]
Chapter VI. Iteration in Procedural Programming
:[font = title; inactive; preserveAspect]
18. Iterative Loops I: While
:[font = smalltext; inactive; preserveAspect]
Last revision: September 25 1996
:[font = text; inactive; preserveAspect]
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.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
Loops and Efficiency
:[font = text; inactive; preserveAspect; endGroup]
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.
:[font = section; inactive; Cclosed; preserveAspect; startGroup]
The While Construct
:[font = text; inactive; preserveAspect]
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.
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Example 1: Finding a Negative; Classic Principles of Loops
:[font = text; inactive; preserveAspect]
How can we find the first negative number in a list of numbers?
:[font = subsubsection; inactive; Cclosed; preserveAspect; startGroup]
List-operation solution
:[font = input; preserveAspect]
Clear[firstNeg];
firstNeg[x_List] := First[ Select[x, (#<0&)] ]
:[font = input; preserveAspect]
firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]
:[font = text; inactive; preserveAspect; endGroup]
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.
:[font = subsubsection; inactive; Cclosed; preserveAspect; startGroup]
While loop solution; Classic Principles
:[font = input; preserveAspect]
?While
:[font = input; preserveAspect]
firstNeg[x_List] := Module[{i},
i = 1;
While[ x[[i]]>=0, i=i+1 ];
x[[i]]
]
:[font = input; preserveAspect]
firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]
:[font = text; inactive; preserveAspect]
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.
:[font = text; inactive; preserveAspect]
Our example contains each of the following classic principles of an
iterative loop:
:[font = text; inactive; preserveAspect]
1. We initialize one or more variable(s) before entering the loop. These
variables are typically local.
:[font = text; inactive; preserveAspect]
2. We modify the variable(s) each time through the loop. In the example
above, we increment "i" by 1 every time.
:[font = text; inactive; preserveAspect]
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.
:[font = text; inactive; preserveAspect; endGroup]
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.
:[font = subsubsection; inactive; Cclosed; preserveAspect; startGroup]
While loop solution with error handling
:[font = text; inactive; preserveAspect]
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?
:[font = input; preserveAspect]
firstNeg[{3,5,2,4,3,11,0,8}]
:[font = text; inactive; preserveAspect]
The first eight entries were non-negative, so it tried the ninth---but
there is no ninth element.
:[font = text; inactive; preserveAspect]
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.
:[font = input; preserveAspect]
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]]
]
]
:[font = text; inactive; preserveAspect]
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".
:[font = input; preserveAspect]
firstNeg[{3,5,2,-7,4,3,11,-2,0,-1,8}]
:[font = input; preserveAspect; endGroup; endGroup]
firstNeg[{3,5,2,4,3,11,0,8}]
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Example 2: Finding the first prime beyond n.
:[font = text; inactive; preserveAspect]
Recall "PrimeQ[ ]": a boolean test for a prime number. Here we use it to
find the first prime number beyond "n":
:[font = input; preserveAspect]
?PrimeQ
:[font = input; preserveAspect]
firstPrimeBeyond[n_Integer?Positive] :=
Module[{i},
i = n+1;
While[ Not[PrimeQ[i] ], i++];
i
]
:[font = input; preserveAspect]
firstPrimeBeyond[20]
:[font = text; inactive; preserveAspect]
(Note our use of the increment notation "i++".) There are two tempting
pitfalls to dodge in trying to simplify the code above, as follows:
:[font = subsubsection; inactive; Cclosed; preserveAspect; startGroup]
Pitfall 1: The While command does not have a return value.
:[font = input; preserveAspect]
Clear[firstPrimeBeyond];
firstPrimeBeyond[n_Integer?Positive] :=
Module[{i},
i = n+1;
While[ Not[PrimeQ[i]], i++]
]
:[font = input; preserveAspect]
firstPrimeBeyond[20]
:[font = text; inactive; preserveAspect; endGroup]
The "While[ ]" loop executed correctly, but provided us with no answer.
:[font = subsubsection; inactive; Cclosed; preserveAspect; startGroup]
Pitfall 2: Formal parameters cannot be used in place of local variables
because formal parameters cannot be modified within a Module.
:[font = text; inactive; preserveAspect]
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".
:[font = input; preserveAspect]
Clear[firstPrimeBeyond];
firstPrimeBeyond[n_Integer?Positive] :=
Module[{},
n = n+1;
While[ Not[PrimeQ[n]], n=n+1];
n
]
:[font = input; preserveAspect]
firstPrimeBeyond[20] (* Action, Interrupt this infinite loop. *)
:[font = text; inactive; preserveAspect; endGroup]
(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.)
:[font = text; inactive; preserveAspect; endGroup]
These two pitfalls illustrate why one should generally abide by the three
classic principles stated above.
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Example 3: Programming the fixed-point iteration.
:[font = text; inactive; preserveAspect]
Recall that "FixedPoint[ ]" works like "Nest[ ]" except that it stops when
two consecutive values are recognized as identical.
:[font = input; preserveAspect]
NestList[Cos, 0.0, 20]
:[font = input; preserveAspect]
Nest[Cos, 0.0, 20]
:[font = input; preserveAspect]
FixedPoint[Cos, 0.0]
:[font = input; preserveAspect]
?FixedPoint
:[font = text; inactive; preserveAspect]
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.
:[font = input; preserveAspect]
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 *)
]
:[font = input; preserveAspect]
myFixedPoint[Cos, 0.0]
:[font = text; inactive; preserveAspect; endGroup]
Notice how the second argument of "While[ ]" may be a compound expression
of several lines separated by semicolons, as in a Module.
:[font = subsection; inactive; Cclosed; preserveAspect; startGroup]
Example 4: Listing the prime numbers less than n.
:[font = text; inactive; preserveAspect]
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.
:[font = input; preserveAspect]
Table[Prime[i],{i,1,10}]
:[font = text; inactive; preserveAspect]
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[ ]".
:[font = input; preserveAspect]
primesUpTo[n_Integer?Positive] :=
Module[{i, primeList},
i = 1;
primeList = {};
While[ Prime[i]