Skip to content

Kinds of Loop

Learning Objectives

At the end of this sub-unit, students should

  • appreaciate the relationship between while-loop and mathematics.
  • understand the different kinds of while-loop.
  • know how to identify problems involving different kinds of while-loop and solve them.

Fixed Repetitions

In our first example of while-loop --reproduced below-- the number of repetition is related to the input algebraically. The number is captured by the variable ctx, which is initialized before the loop and updated inside the loop independently of the the result variable res. Given that, we can actually downwards (i.e., ctx = ctx - 1) instead of upwards (i.e., ctx = ctx + 1). The code corresponding to downward counting is also shown below.

1
2
3
4
5
6
7
# Assume k and n are initialized
res = k
ctx = 0
while ctx < n - 1:
  res = res * k
  ctx = ctx + 1
print(res)

1
2
3
4
5
6
7
# Assume k and n are initialized
res = k
ctx = n
while ctx > 0:
  res = res * k
  ctx = ctx - 1
print(res)

There is a simpler way to do this called for-loop, but let us limit ourselves to while-loop for now. Instead, what we want to do is to abstract this into the essence of a computation of exactly \(n\) repetition. As the code above is for \(n - 1\) repetition, we need to do one more repetition, but that is quite straightforward.

Exactly n Repetition

In this case \(n\) can be based on the input or some value computed from the input. For instance, if we rename our input as k, then we can say that n = k - 1 for exponentiation.

1
2
3
4
5
6
7
# Assume n is initialized
# before loop
ctx = 0
while ctx < n:
  # loop-body
  ctx = ctx + 1
# after loop

1
2
3
4
5
6
7
# Assume n is initialized
# before loop
ctx = n
while ctx >= 0:
  # loop-body
  ctx = ctx - 1
# after loop

The real question is, what is the use of categorizing loops in this way? By having a classification, we hope that you can use the template to solve other problems more easily. Let us try this out on the factorial example. To use this template, we need to answer the following questions.

  1. What is \(n\) (i.e., the number of repetition)?
  2. What should be done before the loop?
    • Usually, we initialize the result. What is the initial value of res.
  3. What is the loop-body?
    • Usually, we update the result res. What is the update?
  1. What is \(n\) (i.e., the number of repetition)?      \(n\) times
  2. What should be done before the loop?
    • Usually, we initialize the result. What is the initial value of res?      res = 1
  3. What is the loop-body?
    • Usually, we update the result res. What is the update?      res = res * (ctx + 1)
1
2
3
4
5
6
7
# Assume n is initialized
res = 1
ctx = 0
while ctx < n:
  res = res * (ctx + 1)
  ctx = ctx + 1
print(res)

This is a preview of the preferred problem solving technique called pattern matching.

Summation and Product

Mathematically, we can represent exponentiation and factorial as products.

\[ k^n = {\displaystyle \prod_{i = 1}^{n} k} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n! = {\displaystyle \prod_{i = 1}^{n} i} \]

There is another big operator called summation. It has major usage in mathematics as we can approximate many functions as summation called Taylor's series1. Let us look at one of this. We will choose the simplest one where the loop-body can be done as a single line.

\[ \text{ln}(1 + x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots = {\displaystyle \sum_{i = 1}^{\infty} (-1)^{i + 1} \frac{x^i}{i}} \]

Unfortunately, the computation requires an infinite number of computations. But our time here is finite, so we cannot compute this with an arbitrary precision. Instead, we will approximate this with \(n\) number of repetitions. So the formula with the added \(n\) now becomes the following.

\[ \text{ln}(1 + x)_n = x - \frac{x^2}{2} + \frac{x^3}{3} - \cdots + (-1)^{n + 1} \frac{x^n}{n} = {\displaystyle \sum_{i = 1}^{n} (-1)^{i + 1} \frac{x^i}{i}} \]

And now, we can solve this with the template from before as there are exactly \(n\) repetitions. There is a slight change to the initial value and the loop-condition. We will start from 1 and check <= n. This match the formula more closely.

We also rename ctx to i to match more closely with the formula. In fact, i is the most common name for the iteration variable because it is short2. Also, if we are always using i as iteration variable, then it is actually descriptive.

Natural Logarithm

1
2
3
4
5
6
7
# Assume x and n are initialized
res = 0
i = 1
while i <= n:
  res = res + (((-1) ** (i + 1)) * (x ** i) / i)
  i = i + 1
print(res)

A brief side-note, this formula is not actually useful for \(x > 1\). So you should test it with \(0 \leq x \leq 1\). Take for example, \(\text{ln}(1.5) = 0.4054651081081644\). By initializing x = 0.5 and n = 10, we get 0.4054346478174603. That is pretty close.

In short, mathematical summation and product are simply loops. However, the opposite may not be true as there are some loops that are not exactly summation or product. For numerical problems, you may want to think about loops as a shorthand for summation and product first.

Arbitrary Repetitions

In computing the natural logarithm, we notice a potential problem. The first problem we may notice is how do we choose a good value of \(n\) for the approximation. We can try to list the values for different \(n\) to see the impact. We will keep only 5 decimal places due to space constraints.

\(x\) \(\text{ln}(1 + x)\) \(n = 1\) \(n = 2\) \(n = 5\) \(n = 10\) \(n = 15\)
0.1 0.09531 0.1 0.095 0.09531 0.09531 0.09531
0.1 0.18232 0.2 0.180 0.18233 0.18232 0.18232
0.5 0.40546 0.5 0.375 0.40729 0.40543 0.40546
0.9 0.64185 0.9 0.495 0.69207 0.62620 0.64183
1.0 0.69314 1.0 0.500 0.78333 0.64563 0.72537

So the value of \(n\) can be small for small \(x\) but it needs to be larger for larger \(x\). Surely there is a way we can find a good \(n\) for each \(x\) but unless we are expert in mathematics, we may not even know how to find such \(n\). What is the alternative?

One alternative is to compute the value up to some precision level. Let us say we want to achieve precision level of 3 decimal places. How many repetition will that take? The good thing is, we do not have to know. If we assume that the result will converge into the true value (e.g., if \(x \leq 1\)), then the absolute difference between consecutive iteration is within 3 decimal places.

To be more precise, \(|\text{ln}(1 + x)_{n} - \text{ln}(1 + x)_{n + 1}| < 0.001\). Looking at the formula, the difference is exactly the \(n\)th term.

\[ |(-1)^{n + 2} \frac{x^{n + 1}}{n + 1}| \]

So we stop when this value is smaller than 0.001. Do not forget that we are using while-loop and in while-loop, the condition is the condition to keep on continuing executing the loop-body. We need to negate the condition. As such, the loop-condition is the following.

\[ |(-1)^{n + 2} \frac{x^{n + 1}}{n + 1}| \geq 0.001 \]

Note that it should not really matter if we use \(\geq\) or \(>\) because we are using floating point number and it is already an approximation. Putting things together, we get the following code. We can use the function abs(val) to find the absolute value of val. This is similar to how we use print or input.

Precise Natural Log

1
2
3
4
5
6
7
8
9
# Assume x is initialized
res = 0
i = 1
val = (((-1) ** (i + 1)) * (x ** i) / i)    # compute next term
while abs(val) >= 0.001:                    # independent of n
  res = res + val
  i = i + 1
  val = (((-1) ** (i + 1)) * (x ** i) / i)  # do not forget to recompute next term
print(res)

Infinite Loop

Now that we have separate the loop from a fixed number of pretitions (e.g., from \(n\)), we may have additional problems. Remember how the code above is only meaningful for \(x \leq 1\). What happen if we have \(x > 1\)? Consider the fraction in the term for the formula.

\[ \frac{x^{n + 1}}{n + 1} \]

When \(x \geq 1\), the numerator \(x^{n + 1}\) will increase much more rapidly than the denominator \(n + 1\). This means that this value will never be smaller than 0.001. So now, the condition will always be satisfied. In other words, the loop will never terminate. This is a possibility for a while-loop3 that we have to be cafeful of4.

A simpler example of an infinite loop happen when the loop-body does not modify the variables used in the loop-condition. So the evaluation of the loop-condition will always produce the same value. An even simpler one is simple the following.

1
2
while True:
  print("Dormammu, I've come to bargain!")

Collatz Conjecture

The potential for infinite loop shows the capability of the programming language. Usually, when a general purpose programming language is capable of producing an infinite loop, it means it can theoretically compute everything that can be computed. We will illustrate this with an open problem in mathematics. This problem is called the Collatz conjecture. The problem can be described as follows.

Collatz Conjecture

Given a positive integer \(n\), we can compute the next value of \(n\) as follows.

  • If \(n\) is even (i.e., divisible by 2), then the next \(n\) is computed as \(n = n \div 2\).
  • If \(n\) is odd (i.e., not divisible by 2), then the next \(n\) is computed as \(n = 3n + 1\).

The conjecture states that if we start from any positive \(n\), performing the computation above will eventually produce \(n\) equals to 1.

Nobody knows if the conjecture is true or not, but it has been checked for very large numbers. By being able to code potentially infinite loop, we do not care if the conjecture is true or not. If the conjecture is false, our code will simply never terminate. This gives some argument on why infinite loop show the computational capability of the language.

To make this into a computational problem, instead of checking numerically if the conjecture is true, we want to know for a given \(n\), how many steps does it take to reach \(n = 1\). If \(n\) is already 1, we say that it takes 0 step. The solution is shown below, which is just a simple translation from the simulation above.

Collatz Conjecture

1
2
3
4
5
6
7
8
9
# Assume n is initialized
step = 0           # count the step
while n > 1:       # alternatively, while n != 0:
  step = step + 1  # take one step
  if n % 2 == 0:   # n is even
    n = n // 2     #   use // to keep n as integer
  else:            # n is odd
    n = 3 * n + 1  #   3n + 1
print(step)

  1. You do not have to understand this. There are mathematical courses that will explain this. The advantage of programming is that we need not fully understand the underlying problem, we simply need to know how to compute. ↩

  2. Other typical names for iteration variables are j and k. If you are Romans, you may want to use i, ii, iii, iv, v, ... instead. ↩

  3. Actually, for this problem, we have another problem which is OverflowError. This happens because the (x ** i) will produce values so large we cannot represent it easily. ↩

  4. If you do experience an infinite loop (or if you are just too lazy to wait), you can press Ctrl+C to terminate the current execution. ↩