Up to this point, we have seen that we can conditionally execute a block of code using a conditional statement. The body of a conditional statement

	if ( some-condition ) {
		// Consequental body of the conditional statement
	}

will be executed once if the condition is true, and it will never execute if the condition is false.

In some cases, however, we may have to do something not just once but multiple times. To begin with a more humorous example, the game of Pictionary is played as follows: you draw a picture and your team attempts to guess what the image is. If they guess the word, you win; otherwise, you modify the image and allow your team to guess again. In theory, you could repeat this process forever until your team finally guesses that the word was "apathy".

A more humorous flow chart of the game by Doghouse Diaries is represented here:

As a more serious example, in calculating $n!$, we start with $2$, multiply that by $3$ to get $6$, multiply that by $4$ to get $24$, and so on until we finally multiply the last result by $n$.

To implement such an operation, we need some way of performing an operation multiple times, and for that we introduce a while statement:

	while ( some-condition ) {
		// Body of the while loop
	}

If the condition is never true, the body of the loop will never be executed. The flow chart for such a statement is:

We continue doing something until the condition is false.

Now, don't run this next example as we have a potential issue: suppose that the condition is always true. In this case, the loop will continue executing forever:

#include <iostream>

int main();

int main() {
	int n{0};

	while ( n == 0 ) {
		std::cout << "Hello world!" << std::endl;
	}

	return 0;
}

This loop will never exit—it will continue printing Hello world! forever or until you end the execution (Ctrl-c), the computer malfunctions or the next blackout occurs.

A loop that never terminates is called an infinite loop. An infinite loop is likely a problem if you're trying to solve a problem: there are two possible sources of an infinite loop:

• an error with your program, or
• a problem with no solution.

Almost all of your infinite loops for the next two years will be of the first kind; however, when you get to second year, you will be finding approximations to mathematical problems, and the likelihood of the second will increase.

There is, however, one kind of infinite loop that is very common, and actually required: an infinite loop in an embedded system. Consider your Tickle-Me-Elmo^TM where a microcontroller controls the behavior. A microcontroller is a processor usually less powerful than a general-purpose microprocessor found in your laptop or desktop computers, but where some peripherals of laptops and desktops are built into the microcontroller. When you turn on your Tickle-Me-Elmo, the microcontroller runs in a loop waiting for the child to do something to which it should respond.

However, for the purpose of this course, an infinite loop will always be considered a semantic programming error—if you get into an infinite loop, you did something wrong.

Determining if a number is prime

Our first serious example of an algorithm that you learned in secondary school is determining if an integer $n$ is prime. This requires you to try to divide the integer by all integers up to $\sqrt{n}$. We could visualize this as a flow chart:

It is important to understand what the problem you are trying to solve is first before you code it. This is why flow charts are useful: you can give this flow chart to a non-programmer, and that person could reasonably be expected to execute this algorithm.

Note, $\sqrt{n}$ may not be an integer, so instead of checking if $k \le \sqrt{n}$, we will check if $k^2 \le n$.

Long division

Another algorithm you saw in secondary school (and likely in primary school) is long division. While you may have learned the procedure, it's quite unlikely that you could easily write down how someone else could implement this algorithm. Here is one means of performing the operation of long division: Suppose we are calculating $m \div n$. First, we must assume that each number has a finite number of decimal places.

1. First, if both $m$ and $n$ have the same sign, the result will be positive; otherwise, the result will be negative. Thus, our solution begins with either "+" or "-". Now discard the signs of $m$ and $n$.
2. Second, multiply both $m$ and $n$ by the smallest power of $10$ that allows $n$ to be an integer. For example, instead of calculating $39.527 \div 1.73$, we are now calculating $3952.7 \div 173$. Similarly, instead of calculating $35.25 \div 1300$, we are now calculating $0.3525 \div 13$. Update both $m$ and $n$ to be these two new numbers.
3. Third,
• if $|m| < 1$, append a "0." to the solution and let $r$ equal the first digit after the decimal place.
• Otherwise, let $r$ equal the first non-zero digit.
4. Now, iterate:
1. Find the largest multiple $d$ of $n$ such that $r - dn \ge 0$, append $d$ to the solution, and let $r - dn$ be the new $r$.
2. Add the next digit of $m$ to the end of the new $r$ and if the next digit is the first digit after the decimal place, append a decimal point to the end of the solution.

Factorial

The factorial $n!$ is defined as the product of all numbers between $2$ and $n$.

Binomial coefficients

The binomial coefficients $n \choose k$ can be found to be equal to $\frac{n!}{k! (n - k)!}$, which requires the calculation of three separate factorials.

A faster algorithm in finding $n \choose k$ is to first let $k$ be the minimum of $k$ and $n - k$, and to then calculate $\frac{n(n - 1)\cdots(n - k - 1)}{k!}$, which requires a total of only $2k - 2$ multiplications and not $2n - 6$ multiplications.

Greatest common denominator

In calculating the greatest common denominator (gcd) of two positive integers, we have the following flow chart:

Questions and practice:

1. Describe how you would add and multiply two integer real numbers.

2. Describe the algorithm you would follow to subtract one positive integer from another positive integer.

Note that this is potentially more expensive than adding two numbers, as the borrowing process may also require a secondary repetitious sequence of operations.

3. Describe how you would play the game of "High-Low", where you are asked to guess a number between 1 and 100, and if your guess is high, the person says "High", while if your guess is low, the person says "Low".

4. Describe how you would calculate 3.5⁶⁵ if all you had was a calculator that had the four basic arithmetic operations.