Skip to main content
Logo image

MAT 112 Integers and Modern Applications for the Uninitiated

Sebastian Pauli

Section 2.5 The Loop repeat_until

Loops allow us to repeat sequences of instructions. In a repeat_until -loop a sequence of instructions is repeatedly followed until a specified statement is true.
A repeat_until -loop starts with a repeat instruction and ends with a until instruction. The instructions between repeat and until are followed (in order) until the statement after until is true. If you follow the algorithm and get to the instruction until and the statement after until is false, you jump back to repeat and execute the first instruction after repeat.
Every time we follow the instructions between repeat and _until we call an iteration of the ( repeat_until )-loop. We call the first time we follow these instructions the first iteration and so on.
Our first algorithm with a repeat_until -loop subtracts \(2\) from a given natural number \(n\) until we get number that is less than \(2\text{.}\) When the number is even the output is \(0\) , when the number the output is \(1\text{.}\)
We now use Algorithm 2.29 to determine whether \(5\) is even or not.

Example 2.30. Algorithm 2.29 with input \(n=5\).

We follow the instructions of Algorithm 2.29 for the input \(n=5\text{.}\)
Input: \(n=5\)
  1. repeat: A repeat_until -loop starts here
    1. let \(n:=n-2\) : We have \(n=5\text{.}\) We compute \(n-2=5-2=3\) and assign this value to \(n\text{.}\) So now \(n=3\text{.}\)
  2. until \(n\lt 2\text{:}\) We have \(n=3\text{.}\) Since the statement \(n\lt 2\) is false we repeat the instructions in the loop.
  1. repeat: We continue in the repeat_until -loop.
    1. let \(n:=n-2\) : We have \(n=3\text{.}\) We compute \(n-2=3-2=1\) and assign this value to \(n\text{.}\) So now \(n=1\text{.}\)
  2. until \(n\lt 2\text{:}\) We have \(n=1\text{.}\) Since the statement \(n\lt 2\) is true we leave the loop and continue with Item 3.
  3. return \(n\text{:}\) We return the value of \(n\) which is 1.
Output: \(n=1\)
In our next example, given a natural number \(n\) , computes the sum of the natural numbers up to \(n\text{.}\) In the algorithm, \(s\) is the sum so far and \(i\) is incremented in each iteration of the repeat_until loop. The algorithm computes \(1+2+3+\dots+(n-2)+(n-1)+n\text{.}\)
In the Example 2.32 we compute the sum of the natural numbers up to \(4\) with Algorithm 2.31.

Example 2.32. Algorithm 2.31 for the input \(n=4\).

We follow the steps of Algorithm 2.31 for the input \(n=4\text{.}\) For each step of the algorithm, we give the new values of the variables that change values in that step.
Input: \(n=4\)
  1. let \(i:=0\) : So the variable \(i\) has the value \(0\) now.
  2. let \(s:=0\) : So the variable \(s\) has the value \(0\) now.
  3. repeat : A repeat_until -loop starts here.
  3.a. let \(i:=i+1\) : As the old value of \(i\) was zero the new value of \(i\) is \(0+1=1\text{.}\)
  3.b. let \(s:=s+i\) : As the old value of \(s\) was zero and the value of \(i\) is \(1\) the new value of \(s\) is \(0+1=1\text{.}\)
  4. until \(i=n\) : As \(i=1\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a
  3. repeat : We continue the A repeat_until -loop.
  3.a. let \(i:=i+1\) : As the old value of \(i\) was \(1\) the new value of \(i\) is \(1+1=2\text{.}\)
  3.b. let \(s:=s+i\) : As the old value of \(s\) was \(1\) and the value of \(i\) is \(2\) the new value of \(s\) is \(1+2=3\text{.}\)
  4. until \(i=n\) : As \(i=2\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
  3. repeat : We continue the A repeat_until -loop.
  3.a. let \(i:=i+1\) : As the old value of \(i\) was \(2\) the new value of \(i\) is \(2+1=3\text{.}\)
  3.b. let \(s:=s+i\) : As the old value of \(s\) was \(3\) and the value of \(i\) is \(3\) the new value of \(s\) is \(3+3=6\text{.}\)
  4. until \(i=n\) : As \(i=3\) and \(n=4\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
  3. repeat : We continue the A repeat_until -loop.
  3.a. let \(i:=i+1\) : As the old value of \(i\) was \(3\) the new value of \(i\) is \(3+1=4\text{.}\)
  3.b. let \(s:=s+i\) : As the old value of \(s\) was \(6\) and the value of \(i\) is \(4\) the new value of \(s\) is \(6+4=10\text{.}\)
  4. until \(i=n\) : As \(i=4\) and \(n=4\) the statement \(i=n\) is true. We continue with step 5.
  5. return \(s\) : The algorithm returns \(s=10\text{.}\)
Output: 10
In Example 2.33 click your way through the steps of Algorithm 2.31 to see how the values of the variables change with each instruction. When following the loop you have to click on repeat as well as until.

Example 2.33. Algorithm sum interactive.

In the video in Figure 2.34 we introduce repeat_until loops and consider Algorithm 2.31 and Algorithm 2.29 once more.
Figure 2.34. Algorithms -- Loopsby Matt Farmer and Stephen Steward
A repeat_until -loop with a statement that is always false in the repeat instruction yields a never ending loop. A sequence of instructions (even if this is only the case fore certain input values) that contains such a loop is not an algorithm.

Example 2.35. Infinite loop.

We give an example of a sequence of instructions that gets caught in a never ending loop for certain input values.
Input: an integer \(a\)
  1. let \(m:=1\)
  2. repeat
    1. let \(m:=m\cdot a\)
    2. let \(a:=a-1\)
  3. until \(a=0\)
  4. return \(m\)
When the input \(a\) is 0 or a negative integer, this sequence of commands does not end. It never reaches the instruction return \(m\) since \(a\) will never be 0. In this case we do not have a finite sequence of instructions, so it does not match the definition of an algorithm ( Definition 2.1 ).

Problem 2.36.

With the algorithm below answer the following questions:
  1. Follow the steps of the algorithm for \(b=5\) and \(n=3\text{.}\)
  2. What does the algorithm return for the input \(b=-2\) and \(n=6\text{.}\)
  3. What does the algorithm compute?
Solution.
  1. We follow the algorithm for the input \(b=5\) and \(n=3\text{.}\) For each step with an assignment we give the new value of the variable.
    Input: \(b=5\) and \(n=3\)
      1. \(c=0\)
      2. \(i=0\)
      3. A repeat_until -loop starts
      3.a. \(c=5\)
      3.b. \(i=1\)
      4. As \(i=1\) and \(n=3\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
      3. We continue in the repeat_until -loop.
      3.a. \(c=10\)
  2.   3.b. \(i=2\)
      4. As \(i=2\) and \(n=3\) the statement \(i=n\) is false. We repeat the loop and continue with step 3.a.
      3. We continue in the repeat_until -loop.
      3.a. \(c=15\)
      3.b. \(i=3\)
      4. As \(i=3\) and \(n=3\) the statement \(i=n\) is false. We exit the loop and continue with step 5.
      5. We return the value of \(c\) which is \(15\text{.}\)
    Output: 15
  3. Proceeding as above we find that for the input \(b=-2\) and \(n=6\) the algorithm returns \(-12\text{.}\)
  4. Until \(i\lt n\) the algorithm adds \(b\) to \(c\) and adds \(1\) to \(n\text{.}\) Thus the number of times \(b\) is added to \(c\) is \(n\text{.}\) As initially \(i\) is set to 0 (see step 2 ) the number of times \(b\) is added to \(0\) is \(n\text{.}\) So the output of the algorithm is \(n \cdot b\text{.}\) Also compare Definition 1.31 where we had defined multiplication as repeated addition.
We refer to this algorithm in the following two problems.

Problem 2.39. Algorithm 2.38 with input \(n=3\).

Follow the instruction in Algorithm 2.38 when the input is \(n=3\text{.}\) We only list the steps in which the values of a variable changes.
Solution.
We follow the algorithm for the input \(n=3\text{.}\)
Input: \(n=3\text{.}\)
  1. let \(f:=1\)
  2.a. let \(f:=1\cdot 3=3\)
  2.b. let \(n:=3-1=2\)
  3. As \(n=2\) the statement \(n=1\) is false. To repeat the loop we continue with step 2.a.
  2.a. let \(f:=3\cdot 2=6\)
  2.b. let \(n:=2-1=1\)
  3. As \(n=1\) the statement \(n=1\) is true. We exit the loop and continue with step 4.
  4. We return the value of \(f\) which is \(6\text{.}\)
Output: 6
Now that we have gone through the algorithm instruction by instruction for a specific input we have a better idea what the algorithm computes.

Problem 2.40. What does Algorithm 2.38 compute ?

What does Algorithm 2.38 compute ?
Solution.
For the input value \(n\text{,}\) the output of the algorithm is
\begin{equation*} 1\cdot n\cdot (n-1)\cdot\ldots\cdot2. \end{equation*}
So, the algorithm computes the product of the natural numbers up to \(n\text{.}\)
The product of the natural numbers up to \(n\) is important enough to have a name.

Definition 2.41.

Let \(n\) be a natural number. The product
\begin{equation*} 1\cdot 2\cdot 3\cdot\dots \cdot(n-1)\cdot n \end{equation*}
is called \(n\) factorial. We denote \(n\) factorial by \(n!\text{.}\)
In Checkpoint 2.42 we unroll the loop in Algorithm 2.38. Follow the instructions to find the factorial of the input.

Checkpoint 2.42. Compute a factorial with Algorithm 2.38.

Consider the following algorithm.
Algorithm Factorial
Input: A natural number \(n\)
Output: \(n!\)
(1) let \(f:=1\)
(2) repeat
-- (a) let \(f:=f\cdot n\)
-- (b) let \(n:=n-1\)
(3) until \(n=0\)
(4) return \(f\)
Now use the algorithm to compute the factorial of \(n=5\text{.}\)
Input: A natural number \(n =\) .
(1) let \(f:=1\text{.}\)
(2) repeat
-- (a) let \(f:=f\cdot n=\)
-- (b) let \(n:=n-1=\)
(3) Because the statement \(n=1\) is false, the loop is repeated. We continue with step (2).
(2) repeat
-- (a) let \(f:=f\cdot n=\)
-- (b) let \(n:=n-1=\)
(3) Because the statement \(n=1\) is false, the loop is repeated. We continue with step (2).
(2) repeat
-- (a) let \(f:=f\cdot n=\)
-- (b) let \(n:=n-1=\)
(3) Because the statement \(n=1\) is false, the loop is repeated. We continue with step (2).
(2) repeat
-- (a) let \(f:=f\cdot n=\)
-- (b) let \(n:=n-1=\)
(3) Because the statement \(n=1\) is true, the loop ende. We continue with step (4).
(4) return \(f\)
Output: \(f =\)
described in detail following the image
A figure sits at a desk with a monitor and a laptop on it. The figure is holding a tablet and a smartphone.
The following caption is laid out as a circle: Stare blankly at screen, open news site, start reading, get bored, absently check smaller device, stare blankly at screen
Ugh, today’s kids are forgetting the old-fashioned art of absentmindedly reading the same half-page of a book over and over and then letting your attention wander and picking up another book.
Ugh, today’s kids are forgetting the old-fashioned art of absentmindedly reading the same half-page of a book over and over and then letting your attention wander and picking up another book.
Figure 2.43. Loopby Randall Munroe ( https://xkcd.com/1411 ).
PrevTopNext