Math 451: Computational Mathematics

2.4 Loop Structures

---

2.4.1 Loop Structures

A Loop Structure defines a code block that is executed multiple times in succession. In computational mathematics we often need to perform the same operation on a vector or array of numbers, or perform several similar operations on the data. The body of a loop structure is the code block that is executed multiple times. An iteration of the loop structure occurs each time the body of a loop structure is executed. The number of times the body of the loop structure is iterated is called the loop count . We say that the algorithm iterates the code block.

2.4.2 Indefinite Loop Structures

An Indefinite Loop Structure or Conditional Loop Structure iterates the body of the loop structure until certain conditions are met.

Figure 1

In MATLAB the keyword while declares an indefinite or conditional loop structure. The code block of the while loop structure is terminated by a end MATLAB statement. Thus the code block is indented on tab farther to the right from the while and associated end statements. This makes it easy for everyone to visually demarcate the iterated code block. This loop structure is called indefinite or conditional because like a conditional structure the while statement must include a logical expression, the condition .

• If the condition is satisfied ( TRUE ) execution proceeds to the body of the loop, otherwise execution proceeds to the first MATLAB statement following the associated end statement.
• If all statements in the body of the loop structure execute successfully execution proceeds to the associated end statement.
• The end statement always passes execution back to the while statement.

This means the condition is evaluated again and the result of the logical expression will determine the flow of control at runtime. Thus it is not possible to know before the function executes, how many times the body of the loop structure will be iterated. That is why we call this an indefinite loop structure. The conditional expression in the while statement can not usually be known until runtime.

It is possible for an indefinite loop structure to be an infinite loop . The statement while true indicates that the condition will always be satisfied and the body of the loop structure will be unconditionally iterated. If we leave such a loop in our algorithm it will never stop.

Figure 2

In order to cease iteration of the loop block, we include a condition structure in the body. If the condition is satisfied, the MATLAB statement break is executed in the if block. The break statement tells the MATLAB interpreter to exit the body of the loop and pass control the the first MATLAB statement after the end statement of the loop structure.

One must always include a condition of the while loop or a conditional structure in the body that causes iteration of the loop to cease. Such a condition is called an end condition . When designing an indefinite loop, always plan for a condition that ceases execution of the loop block so that your algorithm stops.

2.4.3 Definite Loop Structures

A definite loop structure is the opposite kind of loop structure from the indefinite loop structure. The number of iterations of the loop is determined when the statement is parsed by the interpreter or compiler. Definite loops are also called counted loops because they include a loop index that is incremented after the successful execution of the loop block. A definite loop structure must have a sequence or list of values associated with the loop structure.

• the loop index is assigned the first element of the list
• the loop block is executed
• if there are more elements in the list, the loop index is incremented to the next element of the list and execution proceeds to the previous step.
• if there are no more elements in the list, execution proceeds to the first MATLAB statement after the associated end statement.

In MATLAB a for statement declares a definite loop structure. The for statement declares two types of execution; an assignment and a condition.

Figure 3

The MATLAB definite loop statement consists of the keyword for followed by an expression that appears to be an assignment statement; it is not! For example

>> for k=1:10

Following the keyword for the statement must contain

• a name for a variable to contain the loop index
• the equal sign
• a vector(one dimensional array) of any MATLAB data type

Recall that the expression 1:10 creates a vector of integers [ 1 2 3 4 5 6 7 8 9 10 ] This statement results in three separate executable segments of the algorithm

1. An assignment initializing the loop index variable
2. A condition that tests if the loop index variable contains more values
3. An assignment that increments the loop index variable to the next element of the list

The two assignments must be the justification for using the equal sign , usually the assignment operator in this statement.

In the loop block, the loop index variable will be in the workspace and contain a value from the vector specified in the for statement. The body of the loop is iterated once with the loop index variable assigned each value of the list. After the body is iterated with the loop index assigned the last value in the list, execution proceeds to the first MATLAB statement after the associated end statement.

Like an indefinite loop, the body of an definite loop may contain a conditional structure with an end condition that terminates execution of the loop structure. The loop index variable is still in the workspace after termination of the loop structure. The value in the loop index variable will be the value assigned to it when the loop structure was terminated.

2.4.4 Pre-test and Post-test Loop Structures

The while loop and for loop structures are pre-test loops ; that is the end condition is evaluated before iterating the loop block. This means it is possible that the body of these loop structures will never be iterated.

Other programming languages use other keywords to declare post-test loops ; loops whose end condition is evaluated after iterating the loop block. In MATLAB one implements a post-test loop by evaluating an end condition in the body of the loop. In Particular when the end condition is evaluated last in the flow of execution of the code block, the resulting loop is a post-test loop. Utilization of a pre-test loop or a post-test loop is usually a matter of programmer style.

Early exercises and homework problems will specify a particular loop and style. Later assignments will leave these details to the student. For now we need to familiarize ourselves with some common loop patterns . A loop pattern is a particular use of loops for a certain type of programming task.

2.4.5 Interactive Loops

An interactive loop iterates a loop block based on the demands of the user. Consider an ATM function that asks the user for a transaction type. Acquiring the transaction type from the user and executing the requested transaction is the body of the loop. At the end of the loop, the ATM function asks the user if they have another transaction. This is a post-test infinite loop. The ATM function will continue to iterate the loop until the user either answers negatively when prompted for more transactions, or the function times out indicating that the user has abandoned the ATM.

2.4.6 Sentinel Loops

A sentinel loop iterates the loop block until data in the workspace contains a distinguishable value . This loop is similar to the interactive loop because the negative response to the prompt can be considered the sentinel value . However user interaction is not required. The sentinel value is not processed like actual data values in the workspace.

• An algorithm processing a cell array of strings may use a null string , "" , to indicate the end of the array of strings.

• A variable length character vector may include a null character , 0x0 as the last character in the variable length vector to indicate the end of the vector.

• A sequence of values streamed over the Internet to a detector may indicate the end of the stream with a sentinel value, for example -1 .

• A function sending a real time stream of video may terminate streaming when a TEARDOWN request is received.

2.4.7 End of File Loops

An End of File Loop opens a file and processes every line of the file until and EOF condition occurs. We will discover file processing in a future section. Like the sentinel loop, this algorithm pattern opens a file and reads the file one line at a time. It processes each line until the last line in the file has been processed.

User interactions, sentinel values, and EOF conditions are all end conditions . The important idea here is that both definite and indefinite loops must have end conditions designed into the algorithm so that it will eventually complete execution and stop.

If the end condition is known when the loop statement is parsed, we have a definite loop such as a for loop. Notice that the end condition of a definite loop may be based on the value of a variable. However when the MATLAB for statement is parsed, the values array is known. Therefore the number of iterations is known.

In an indefinite loop, all of the values in the while logical expression may change during the execution of the body of the loop. Iteration continues until the condition is unsatisfied. The value of the end condition and hence the number of loop iterations can not be know until runtime.

2.4.8 Exercises

1. horner.m

Given a polynomial

$$ p(x) = \displaystyle\sum_{k=1}^n a_kx^{n-k} = a_1x^{n-1} + a_2x^{n-2} + \cdots + a_{n-2}x^2 + a_{n-1}x + a_n, $$
we need a good method of accurately computing the value of the polynomial even when $n$ is large, $x$ is large or $x$ is small. We need to avoid computing $x^k$ for larges value of $k$ or $x$, or small values of $x$. We can factor the polynomial

$$ p(x) = (((((a_1x + a_2)x + a_3)x + \cdots + a_2)x + a_{n-2})x + a_{n-1})x + a_n $$
For example, the polynomials

$$ \begin{align*} [\,1,\ 2,\ 1\,] &= x^2 + 2x + 1 = (1x + 2)x + 1 \\ [\,1,\ -2,\ 3\,] &= x^2 - 2x + 3 = (1x - 2)x + 3 \\ [\,-3,\ -2,\ 3, -4, 5, -6\,] &= ((((-3x - 2)x + 3)x - 4)x + 5)x - 6 \end{align*} $$
We are talking about synthetic division . Recall that to evaluate a polynomial $p$ at $a$, we can use the remainder from synthetic division by $x-a$. Consider the polynomial $p = [\,1,\ -2,\ -15,\ 20,\ 44,\ -48\,]$. We want to evaluate $p(-1)$:

$$ \begin{array}{c|cccccc} -1 & 1 & -2 & -15 & 20 &\ 44 & -48 \\ & & -1 & 3 & 12 & -32 & -12 \\ \hline \\ & 1 & -3 & -12 & 32 & 12 & -60 \end{array} $$
Now we have $p(-1) = -60$.

To evalue $p(2)$:

$$ \begin{array}{c|cccccc} 2 & 1 & -2 & -15 &\ 20 &\ 44 & -48 \\ & &\ 2 &\ \ 0 & -30 & -20 &\ 48 \\ \hline \\ & 1 &\ 0 & -15 & -10 &\ 24 &\ \ 0 \end{array} $$
Now we have $p(2) = 0$. The algorithm for computing the value of a polynomial using synthetic division is call Horner's Method .

Write a function horner in horner.m that computes the value of an input polynomial p using Horner's method at input value x using a for loop. That is use the declaration

function y = horner(p, x)

   % compute y = p(x) using a for loop

end

If $x$ is an array of inputs, your function should return an array y of the values of $p(x)$ for every element of input array $x$. Consider the following

y = zeros(size(x));

    for i=1:numel(x)
        % compute y(i) = p(x(i)) using Horner's method and a for loop
    end

Your function should make sure that the input $p$ is an $1\times n$ array of double precision floating points real numbers, and that $x$ is an array of double precision floating point real numbers.

2. HarmonicNumber.m

Write a function

function h = HarmonicNumber(n)

that returns the $n^{\text{th}}$ Harmonic number using a for loop. The infinite series

$$ \displaystyle\sum_{k=1}^{\infty} \dfrac{1}{k} = \displaystyle\lim_{n\rightarrow\infty}\displaystyle\sum_{k=1}^{n} \dfrac{1}{k} = \infty $$
diverges , however it diverges very slowly. The partial sums of this series

$$ H(n) = \displaystyle\sum_{k=1}^{n} \dfrac{1}{k} $$
are called harmonic numbers .

Write a function HarmonicNumber in file HarmonicNumber.m that computes the $n^{\text{th}}$ harmonic number using a for loop. Your function should return only the specified harmonic number(s). If the input is an array of harmonic numbers, your function should use a for to compute the specified harmonic number for each element of the array. Consider the following loop

harmonic_number = zeros(size(n));

    for i=1:numel(n)
        % compute the n(i)th harmonic number using a for loop
    end

The MATLAB function numel returns the number of elements in the input array . In this way your function will return an array harmonic_number that is the same size as the input array. You should compute the harmonic number of order n(i) and place the value in element harmonic_number(i) . You should compute the harmonic number of order n(i) using a for loop.

Your function should make sure that the input $n$ is an array of positive integers, even if it is a $1\times 1$ array of positive integers.

3. floatpi.m

The MacLaurin series for $\arctan(x)$ centered at $x=0$ is given by

$$ \arctan(x) = \displaystyle\sum_{n=0}^{\infty} (-1)^n\dfrac{x^{2n+1}}{2n+1} $$
Moreover we know that $\tan\left(\frac{\pi}{4}\right) = 1$. Hence

$$ \dfrac{\pi}{4} = \arctan(1) = \displaystyle\sum_{n=0}^{\infty} (-1)^n\dfrac{1^{2n+1}}{2n+1} $$
This yields a series representation for $\pi$,

$$ \pi = \displaystyle\sum_{n=0}^{\infty} (-1)^n\dfrac{4}{2n+1} $$
Therefore we can approximate the value of $\pi$ as follows

$$ \begin{align*} \pi &= \displaystyle\sum_{n=0}^{\infty} (-1)^n\dfrac{4}{2n+1} \\ \\ &= \dfrac{4}{1} - \dfrac{4}{3} + \dfrac{4}{5} - \dfrac{4}{7} + \dfrac{4}{9} - \dfrac{4}{11} + \dots \end{align*} $$

Write a function floatpi in file floatpi.m that returns the MacClauren series approximation to $\pi$ using the first $n$ terms of the series using a for loop. Your function should make sure that the input $n$ is a positive integer. The only output will be the approximation to $\pi$.

Your use of this self-initiated mediated course material is subject to our Creative Commons License .

Creative Commons Attribution-NonCommercial-ShareAlike 4.0


Attribution
You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.


Noncommercial
You may not use the material for commercial purposes.


Share Alike
You are free to share, copy and redistribute the material in any medium or format. If you adapt, remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.