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.

19. Iterative Loops II:  Do, For

Last revision:  November 7 1996

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.

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 2^n > "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=1, 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]".