Chapter 6: Introduction to Programming

The following are number of advanced techniques in Matlab. Again, these are general ideas that appear in any CAS, but the format will be specific to Matlab. We will use these techniques to solve more complicated series of mathematical steps in a nice way. The following techniques are described here:

functions A function in computer science is similar to that of a mathematical function, however, but allow more complicated steps to occur.
boolean values A boolean is something that is either true or false.
if and while statements An if statement allows a few statements of code to branch depending on some condition.
loops A loop is a few statements of code that is run generally a fixed number of times. There are while loops that repeat a block of code while some condition is true. There are also for loops that repeat a block of code a fixed number of times.
recursion Recursion is a type of procedure that allows code to call itself. Although often you can generate code that duplicates recursive code, it is often clearer to understand and often come directly from mathematical statements.

Functions

In Matlab, functions (much like in other computer languages) have one or more inputs and the result is some output (numbers, a plot, an expression). All of the commands that we have seen so far that are built-in to Matlab are functions.

The mathematical functions that we have encounted in this course are a bit different that what we are talking about here. We can define a square function with

function y = f(x)
  y = x^2;
end

A few things to note with this

If we want to do something (like plot) $x^2$, there are easier ways than this.
We must define this at the bottom of a live script.
There is only one input, that we call x.
The output is the variable that is defined as y in the function.
Functions can allow more complicated structures as we will see.
You can call this in the same way, $f(2),f(-2)$ for example.
The semicolon inside a function suppresses any ouput.
The indentation help with readability. It isn’t needed, but help to understand the interior of a function.

Let’s also examine a similar function that adds numbers:

function result = add(x,y)
  result = x + y;
end

In this case, note that there are two inputs, called x and y.
Add it to the bottom of the script you are working on.
Trying running it to make sure it worksw with add(2,3) or add(-7,8).

Exercise: Functions

remove the semicolon from the end of the line in the funtion, reenter it and see what happens. Can you understand what is going on?
Write a function called mult that multiplies two numbers and returns the product. Test it to make sure it works.
Write a function called average that returns the average of three numbers. Test it to make sure it works.

Boolean values and `if` statements

A boolean value is something that is either true or false. These are built-in constants in Matlab. Sometimes we will want to know if a statement is true or false, but generally, we will use them in other structures.

Booleans in Matlab return as 1 (for true) or 0 (for false). This was common to other languages developed in the 1980s, but is kind of a pain, but a philosophy for Matlab is nearly everything is a numeric array. If we just type

true

You will see that the result is 1 (however it does says logical, another word for boolean). false will return 0.

if statements

An if statement is often used inside of a procedure to do different things depending on the value of a variable. Consider the piecewise version of the absolute value. Mathematically, we write: $|x| = \begin{cases} x & x \geq 0 \\ -x & x<0 \end{cases}$

We can make a Matlab procedure for the absolute value the following way:

function result = absol(x)
  if x >= 0
     result = x;
  else
     result = -x;
  end
end

And to help determine if it is correct, evaluate absol(3) and absol(-7).

Testing for Equality and non-equality

To test for equality in Matlab use two equal signs. For example, if we define a variable x=5, then to test if x is 5, try

x==5

will return true.

x==7

will return false. And to test if two things are not equal, use ~=

x ~= 7

Exercise

The modulus of an integer is the remainder in division. For example, 7 mod 3 is 1. In matlab, you can call this function like mod(7,3).

Write a procedure call isOdd that takes a number and returns true if the number is odd and false if not. Use the modulus with the divisor 2.

Loops

A loop is a series of statements that are repeated either a fixed number of times or until a condition occurs. They can be very helpful if a large number of operations need to be done in a predictable manner.

`while` loops

Another very common construction for programming is called a while loop. Basically, we want to run a few statements while some boolean statement is true.

Here’s the general framework

while bool_statement

end

anything can go inside the block and the bool_statement is anything that returns a boolean. This could be a simple check for equality or inequality or calling a function that returns a boolean.

Here’s a simple example:

n=1
while n<10
  n=n+1
end

and you should see as output the individual lines for n. Note the only line inside the while loop is the assignment n=n+1 which takes the current value for the number n adds one to it and then assigns that to n. This is a simple way to update the value of a variable.

And that isn’t very interesting, but we can reproduce the : command crudely in the following way. Let’s say we want to return a list of numbers from 1 to $n$, where $n$ is a positive integer.

function result = intList(n)
  result=ones(1);
  i=2;
  while i<=n
    result(end+1)=i;
    i = i+1;
  end
end

A few things to note about this:

The first line makes an array with a single 1 in it.
The while loop is run with i is less than or equal to n.
The line result(end+1)=i is a way to add another element to the end of an array. In this case we add the next value which is kept track in the variable i.

Let’s run some examples:

typing intList(6) returns [1,2,3,4,5,6]
typing intList(10) returns [1,2,3,4,5,6,7,8,9,10]

Number Theory Examples

The next few examples come from number theory. Since primes are key in this field, we will create functions that test if an integer is prime. Recall the following defintion:

A number $n$ is prime if the only factors are 1 and itself.

If we can find the factors of a number, $n$ then testing for prime isn’t too hard. So we start with a function that finds the factors of the number $n$.

The key part of this is to test if some number, $i$ is a factor. We will use the remainder of $n \div i$ which is built-in as the modulus (mod). For example

mod(7,3) returns 1.
mod(24,4) returns 0

Here’s a function that will find all of the factors of a given number

function factors = findAllFactors(n)
  factors=ones(1); % we know that 1 is a factor of every number
  i=2;
  while i<n
    if mod(n,i) == 0 % if i is a multiple of n, then it's a factor
      factors(end+1)=i;
    end
    i = i+1;
  end
  factors(end+1)=n; % we also know that n is a factor of itself.
end

And here’s a couple of examples of this

type findAllFactors(6) returns [1,2,3,6]
type findAllFactors(29) returns [1,29]

Checking if a number is prime

We mentioned above that an important aspect of number theory is prime numbers. Here’s a function that will test this:

function p = isPrime(n)
  factors = findAllFactors(n);
  p = length(factors)==2; % If there are only two factors, the number is prime.
end

where the boolean length(factors)==2 returns logical true if the length of the factors array is 2 otherwise it is false. This will only be true if the only factors are 1 and n.

These examples not only show how to do some programming but also show how to build up functions based on other functions. Note that since the definition of primality has to do with the number of factors, by using the findAllFactors that we already wrote, it breaks down the problem into simpler pieces.

Another nice use of all factors is the use of a theorem that says that the total number of factors is even (factors pair up) unless the number is a perfect square. We will then use this and the isOdd function you wrote above to write an isPerfectSquare procedure.

function p = isPerfectSquare(n)
  factors = findAllFactors(n);
  p = isOdd(length(factors));
end

Note: there are better ways to check if a number is a perfect square, but this illustrates how to use other functions that we have used to create new functionality

Infinite Loops

Although not what is generally intended, it is common to write a while loop that doesn’t stop (in fact while writing these notes I unintentionally created one). Here’s some things to consider when writing a for loop.

Make sure something is changing in your loop. If you intend to stop the loop on an index, make sure the index is updating.
Look at your code and see if you have something that you think will stop the loop. What ever is in the boolean statement needs to eventually switch.
Stop the code if you need to. To stop any code running in Matlab, enter CTRL-C (that is, hold the control key, then the C character). You can also like the stop button in the bar a
If you can’t figure out why it is in an infinite loop, make sure you don’t have semicolons on lines inside the loop so you can see what’s happening.

Compound booleans in an `if` statement or `while` loop

Recall that a boolean is something that evaluates to true or false and is needed in an if statement or while loop. Often more than one boolean is needed. This is called a compound boolean and is created with either an && for and or an || for or.

An or compound statement. If either or both are true, the result is true, otherwise false.
- true or true is true
- true or false is true
- false or true is true
- false or false is false
An and compound statement. Both must be true to be true, otherwise false
- true and true is true
- true and false is false
- false and true is false
- false and false is false

Here’s an example, where we make an array with all odd perfect squares less than 100. (Note: there is a better way to do this, but the point is to show how to use a compound statement)

% return odd perfect squares up to n
function odd_perfects = oddPerfectSquares(n)
    odd_perfects = ones(1); % 1 is an odd perfect square
    k=2;
    while k<n
        if isOdd(k) && isPerfectSquare(k)
            odd_perfects(end+1) = k;
        end
        k = k+1;
    end
end

More functions with prime numbers

We want to find the smallest prime number bigger than a number n. We will make a procedure that return the next prime.

function p = theNextPrime(n)
  p = n+1;
  while ~isPrime(p)
    p = p+1;
  end
end

The return variable p will start out one larger than n.
The while loop runs while p is not prime.
p is just incremented by 1 each time through.

As some examples:

theNextPrime(17) returns 19
theNextPrime(19) returns 23
theNextPrime(1000) returns 1009

Exercise: Writing a perfect number function

A perfect number is a positive integer $n$, that has the property that the sum of the factors (other than $n$ itself) equals $n$. The two smallest examples are 6 and 28.

The factors of 6 are 1,2,3 and 6. The sum of the first three are 6.
The factors of 28 are 1,2,4,7,14,28. The sum of the first 5 is 28.

We will write a few procedures here to find perfect numbers.

Write a procedure called isPerfect which takes a positive integer, $n$ and return either true or false on whether or not $n$ is a perfect number. (Hint: use the built-in function sum which will take an array of numbers and return the sum. Also, it’s easier to check if the sum of all factors is twice the number $n$)
Test your procedure on some known perfect numbers (6 and 28) and others (like all other numbers less than 100 are not perfect.)
Write a procedure called nextPerfect which takes an integer, $n$ and return the next perfect number greater than $n$.
Test your procedure to find the first few perfect numbers. (Don’t go too big or Matlab will bog down. )

For loops

A for loop is a loop that goes through a list of numbers.

The following is a simple for loop that prints out the numbers 1 to 10

for i=1:10
  i
end

If you want to skip numbers or count backwards, the following

for i=1:2:19
  i
end

for i=10:-1:1
  i
end

and the following adds numbers in a list.

s = 0;
for i=[3, 5, 7, 11, 13, 19]
  s = s+i;
end
s

which returns 58.

Note: there is a command called sum that will also do the above.

sum([3,5,7,11,13,19])

This isn’t a very interesting example, but shows the syntax of a for loop. Often a for loop is used in conjunction with a function. Above, we used a while loop to create an integer list. However, it was a loop with a fixed number of steps in which a for loop is better to use. Here’s a different way to create the integer list:

function result = intList2(n)
  result=ones(1);
  for i=2:n
    result(end+1)=i;
  end
end

This is nearly identical to the intList function above except that we use a for loop which is shorter because we don’t need to include the line that increments the index.

Running intList2(6) returns [1 2 3 4 5 6], which is the same as 1:6.

Recall that the factorial function $n!$ is $n! = 1 \cdot 2 \cdot 3 \cdots n$ and although Matlab has this built-in as factorial, we’ll write our own:

function result = fact(n)
  result = 1;
  for i=1:n
    result = result*i;
  end
end

and the heart of this is that the for loop multiplies all of the numbers from 1 to n together (it does this one step at a time).

Exercise: Examining Factorial Functions

Compare the fact function for a few small nonnegative integers with that of factorial to ensure that they return the same result.

While Loops Versus For Loops

No this, isn’t a smackdown between these two. A big question often is when should I use a while loop and when should I use a for loop. The general rule of thumb is:

If you know that you need to run code for a fixed number of times, use a for loop
If you need to do something to everything in an array, a for loop is good, although there might be other ways without loops to do these.
If you don’t know how many times you need to go through a block of code, use a while loop. Generally this means you need to do something until a condition occurs.

Recursion

Above, we saw how to compute the factorial of a number using a for loop. There’s another way to do this. We can define the factorial in the following way: $n!=\begin{cases}1&n=0\\ n\cdot(n-1)!&\text{otherwise}\end{cases}$

The big difference is that inside the function is a call to the function. This is what is called a recursive function. Often this is very helpful and the factorial is a great example of this. We can write the factorial this way in the following:

function result = factr(n)
  if n==0
    result = 1;
  else
    result = n * factr(n-1);
  end
end

Notice that this looks just like other piecewise functions, like the absolute value, defined above.

Exercise: Checking the Recursive Factorial

Try the function factr for various values of $n$.
Compare the results to the built-in factorial.

Exercise: Fibonacci Numbers

A fibonacci number is defined as $F(1)=1, F(2)=1$, then $F(n)=F(n-1)+F(n-2)$ for $n \geq 3$. This is naturally a recursive function. Write a procedure $F$ that take a positive integer $n$ and returns the $n$th Fibonacci number using recursion. Find the first 20 Fibonacci number.

Hint: First, make sure that you return 1 for n==1 or n==2, otherwise uses the formula given here. To find the first 20 fibonaaci numbers, after defining the fibonacci function, you can use the arrayfun on the array 1:20.

Another Fun Recursive example

Here’s another fun example. A number $n$ is called happy by the following

Take the digits of $n$ and square each one.
Sum the squares.
if the sum is 1, then the number is happy, if not repeat these steps.

Note: it’s also helpful that if this process results in the number 4, then you can never result in a sequence that reaches 1. You can call these number unhappy.

The number 13 is a happy number because $1^{2}+3^{2}=10$ and $1^{2}+0^{2}=1$, so the result ends in 1.
The number 19 is also happy because $1^{2}+9^{2}=1+81=82$, then $8^{2}+2^{2}=64+4=68$, then $6^{2}+8^{2}=36+64=100$, then $1^{2}+0^{2}+0^{2}=1$.
The number $4$ isn’t happy because $4^{2}=16$, then $1^{2}+6^{2}=1+36=37$, then $3^{2}+7^{2}=9+49=58$, then $5^{2}+8^{2}=25+64=89$, then $8^{2}+9^{2}=64+81=145$, then $1^{2}+4^{2}+5^{2}=1+16+25=42$, then $4^{2}+2^{2}=16+4=20$, then $2^{2}+0^{2}=4$ and since we have returned to 4, this will continue cycling, so we stop and say 4 is unhappy.
It has been proven that any unhappy number will eventually hit this cycle.

First, it is helpful to have a procedure that splits any positive integer into its digits. Hereܙs such a function:

function d=splitDigits(n)
  d=arrayfun( @str2double, num2str(n));
end

Basically this works because it takes the number n and turns it into a string and the the function @str2double does the reverse, however applied inside the arrayfun, the string is an array of characters.

Test it a bit with a few numbers.

Then we can write a isHappy procedure in the following way.

function h = isHappy(n)
  if n==1
    h = true;
  elseif n==4
    h = false;
  else
    digits = splitDigits(n);
    sum_of_squares = sum(arrayfun(@(n) n^2,digits)); % sum the squares of the digits
    h = isHappy(sum_of_squares);
  end
end

A few things about this:

This is recursive because in the function it calls itself.
If you want this more compactly, write the last else block as
```
  h = isHappy(sum(arrayfun(@(n) n^2,splitDigits)))
```
which is just a nested version.

Let’s now say that we wish to find all numbers less than 100 that are happy. To run this command on every number between 1 and 100, can be done many ways. A for loop comes to mind, but using the seq command is better:

arrayfun(@isHappy,1:100)

This isn’t very helpful results though. We’ll look at the find function

Finding elements in an array

The find function is very helpful. We’re going to use it to help us understand Happy numbers, but first let’s do some other examples. Define A to be

A=1:10

we can find all of the number greater that 5 with

find(A > 5)

which returns the array [6 7 8 9 10]. This works because A>5 returns true (1) or false (0) for every number that satisfies the condition. Then find returns the array indices of each number that is true.

Another example finds the elements that are even:

find(mod(A,2)==0)

which returns [2 4 6 8 10]

Finding Happy Numbers

Now we return to finding Happy Numbers. Recall that find returns the indices of a matrix that are true and from above, we used the arrayfun to apply isHappy to all of the numbers 1:100. We just nest these:

find(arrayfun(@isHappy,1:100))

returns the numbers: 1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100

Previous Chapter

Return to all notes

Next chapter

Course Notes of Peter Staab

This is where Symbolic Computation class notes are found.

Functions

Exercise: Functions

Boolean values and `if` statements

if statements

Testing for Equality and non-equality

Exercise

Loops

`while` loops

Number Theory Examples

Checking if a number is prime

Infinite Loops

Compound booleans in an `if` statement or `while` loop

More functions with prime numbers

Exercise: Writing a perfect number function

For loops

Exercise: Examining Factorial Functions

While Loops Versus For Loops

Recursion

Exercise: Checking the Recursive Factorial

Exercise: Fibonacci Numbers

Another Fun Recursive example

Finding elements in an array

Finding Happy Numbers

Functions

Exercise: Functions

Boolean values and if statements

if statements

Testing for Equality and non-equality

Exercise

Loops

while loops

Number Theory Examples

Checking if a number is prime

Infinite Loops

Compound booleans in an if statement or while loop

More functions with prime numbers

Exercise: Writing a perfect number function

For loops

Exercise: Examining Factorial Functions

While Loops Versus For Loops

Recursion

Exercise: Checking the Recursive Factorial

Exercise: Fibonacci Numbers

Another Fun Recursive example

Finding elements in an array

Finding Happy Numbers

Boolean values and `if` statements

`while` loops

Compound booleans in an `if` statement or `while` loop