Skip to content

More Loop Combination

Learning Objectives

At the end of this sub-unit, students should

  • appreciate the benefit of thinking in terms of smaller problems.
  • know how to solve problems with nested loop.
  • know how to solve problems with multiple loop.

Taylor Series

Previously, we chose a simple Taylor series that can be solved with a simple loop. Now that we know about nested loop, we can solve more complicated Taylor series. There are a few, we will solve the first one and leave the other as an exercise because the idea is the same.

\[ e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = {\displaystyle \sum_{i = 0}^{\infty} \frac{x^i}{i!}} \]
\[ \text{sin}(x) = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \cdots = {\displaystyle \sum_{i = 0}^{\infty} (-1)^i \frac{x^{2i + 1}}{(2i + 1)!}} \]
\[ \text{cos}(x) = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \cdots = {\displaystyle \sum_{i = 0}^{\infty} (-1)^i \frac{x^{2i}}{(2i)!}} \]

What is the complication here? The formula looks straightforward. However, the computation of \(2!\), \(3!\), \(4!\), and so on requires the computation of factorial. This requires a loop. So we do need nested loop. The first step is to think of factorial as a grey box. Try to think about what the grey box for factorial looks like. The code is reproduced below.

1
2
3
4
5
6
7
# Assume n is initialized
res = 1
val = 1
while val <= n:
  res = res * val
  val = val + 1
# res is n!

Grey05

Now, instead of renaming, we will do the opposite. We want to make sure that any code using the factorial code should not use the following variables: n, val, and res. Then, before copying the code for factorial, we will set up the correct value of n so that the value of \(n!\) is computed.

Since we have the code for factorial, we can not think of it as "solved" and simply assigning the value of n correctly and writing the comment # res <- n! to indicate that we want to use the code to compute the factorial of n. Afterwards, we can use the variable res. Given that, the problem is now much simpler and the partial code is given below. In this code, we will be approximating \(e^x\) up to \(k\) iterations. Note that \(0! = 1\) by definition.

Partial Solution for ex

1
2
3
4
5
6
7
8
9
# input: x, k  (we use k because we cannot use n)
i = 0
e = 0  # local, will be our result
while i < k:
  n = i
  # res <- n!
  e = e + ((x ** i) / res)
  i = i + 1
print(e)

Your task is now to incorporate the code for factorial at Line 6 to replace the comment # res <- n! and actually compute the factorial of n. That will solve the problem for approximating the value of \(e^x\). We can also solve the problem of approximating \(e^x\) up to some precision level but let us try to solve some other problem.

Binomial Coefficient

The binomial coefficient \(\binom{n}{k}\) is used in a lot of places. One of the use is in the expansion of \((x + y)^n\).

\[ (x + y)^n = {\displaystyle \binom{n}{0} x^n y^0 + \binom{n}{1} x^{n-1} y^1 + \binom{n}{2} x^{n-2} y^2 + \cdots + \binom{n}{n-1} x^1 y^{n-1} + \binom{n}{n} x^0 y^n} \]

There are a lot of ways to compute binomial coefficient, but this is not a mathematic course. So the one we will be using is the following with the most number of factorial because know we can compute factorial of any non-negative value \(n\) (i.e., \(n \geq 0\)).

\[ {\displaystyle \binom{n}{k} = \frac{n!}{k! \ (n-k)!}} \]

We will be using the same comments # res <- n! to compute the factorial of n. We need to note that in this case, we can only get the result in the variable res. If we want to use it later, we need to assign it to another variable. This gives us the following partial solution. Note that we solve for \(\binom{m}{k}\) because we cannot use n inside the factorial.

Partial Solution for \(\binom{m}{k}\)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# input: m, k
# compute m!
n = m
# res <- n!
fact_m = res

# compute k!
n = k
# res <- n!
fact_k = res

# compute (m-k)!
n = m - k
# res <- n!
fact_mk = res

binom = fact_m / (fact_k * fact_mk)  # m! / (k! (m-k)!)
print(binom)

Composition

We have shown some simple technique to combine codes that can solve simpler problems to solve larger problems. This is part of a larger problem solving technique. The name for this is called "composition". There are two general ways we can compose codes.

  • Nesting: Seen in Taylor series where we have factorial computation inside another loop.
  • Sequencing: Seen in binomial coefficient where we have multiple different factorial computation.

This is the expected problem solving technique but for now, this is just a glimpse of it. We will explain the technique in more details in the future.