# CS 11 Erlang - Lab 1

## Introduction

This week you will begin to work with the Erlang programming language. Before you can get started, you need to get access to an Erlang emulator. You can either install this on your own computer, or you can work on the machines in the undergraduate CS lab. We will be using Erlang version R15Bxx (e.g. R15B02) for this track. (It is recommended that you install Erlang on your own computer, as the lab version may not be the most up to date.) If you decide to install Erlang on your own machine, you can go to these websites:

You start the emulator by running erl at the command-line. You can then compile modules with the c(module) command, and evaluate Erlang expressions from the prompt. To exit the Erlang emulator, you can type the command q(). which will tell the emulator to shut down. (Note that this command is asynchronous, so it will look like it hasn't done anything, but within a second the emulator will terminate.) You can also exit the emulator in a messier way by hitting Ctrl-C several times in a row.

There is also some very helpful online documentation available at the Erlang website. Here is a link to the R15B02 documentation:

The left frame links to some very helpful material, such as the "Modules" link at the very top, which will tell you all funcitons exported from every module included in the Erlang libraries.

## Part 1: Warm Up

For this part you will create several implementations of the Fibonacci function fib(N), which returns the Nth value in the Fibonacci sequence.

Make sure to follow this specification for fib(N):

• fib(0) = 0
• fib(1) = 1
• fib(N) = fib(N - 1) + fib(N - 2)     (N > 2)

(This is how the Fibonacci sequence is defined on both Mathworld and Wikipedia.)

1. Create a module named "fib", in the file "fib.erl".

2. Create a non-tail-recursive function fib_p that takes a single argument N, and returns the Nth value in the Fibonacci sequence. Use pattern matching on the arguments to specify the various cases for this function.

Add fib_p to your module's export-list, and test it to make sure it works properly.

3. Create another non-tail-recursive function fib_g with the same specification as before, but use guards (i.e. when clauses) to specify the various cases for this function.

Add fib_g to your module's export-list, and test it to make sure it works properly.

(There should be no difference in performance between fib_p and fib_g; implementing both of them will just give you practice with the syntax.)

4. Create a third function tail_fib with the same specification as before, but implement it to be tail-recursive. (You will need a helper function to implement this to be tail-recursive.)

Add tail_fib to your module's export-list, and test it to make sure it works properly.

5. Start an Erlang interpreter, compile your module, and perform these simple experiments. Write your answers to the following questions in a file named "answers.txt".

1. Starting with N = 20, and increasing by steps of 5, how far do you get before fib_p(N) takes more than five seconds to run? Why does it behave this way?
2. How long does it take to compute tail_fib(10000)? Why?

## Part 2: Square-Multiples and the Möbius Function

The Möbius Function is a simple classifier of positive integers, devised by (surprise) August Möbius. Given a positive integer n, the Möbius function μ(n) returns:

• 0 if the number is a multiple of a square
• -1 if the number has an odd number of distinct prime factors
• 1 if the number has an even number of distinct prime factors

The n = 1 case is a special case; μ(1) is defined to return 1.

You can probably see right away that this function is all about generating and then analyzing the list of prime factors for the input value. A number is a multiple of a square if it has any duplicate prime factors; for example, 12 = 2 × 2 × 3, so it is a multiple of a square, and therefore μ(12) = 0.

(If you want to learn about some of the more esoteric qualities of this function then you can look at this page.)

For this section we will focus on one interesting detail about the Möbius Function; runs of square-multiples. We want to write a program that finds the first run of square-multiples of length N. For example, the first run of three square-multiples starts with 48; 48, 49 and 50 are all multiples of squares.

All of your recursive functions for this section should be tail-recursive! Tail recursion is an extremely important aspect of Erlang, so it is important for you to be familiar with it. This section will give you plenty of opportunities to practice implementing tail-recursive functions.

1. Create a module named "mobius", in the file "mobius.erl".

2. Create a function is_prime that takes a single argument N, and returns true if the number is prime, or false if the number is not prime.

Your implementation doesn't need to be particularly fast or clever. For example, you can create a helper function that iterates over integers from 2 to sqrt(N), checking whether N is evenly divisible by each value. If N is not evenly divisible by any value then it is prime; otherwise, it is not prime.

• Hint 1: You can use the remainder operator rem to check if N is evenly divisible by a particular value. A rem B returns the remainder from dividing A by B.
• Hint 2: Computing square-roots is costly. A better approach is to take the test value, which we will call Divisor, and if Divisor × Divisor > N then you are done. (Could be a good when-guard...)

Add is_prime to your module's export-list, and test it to make sure it works properly.

3. Create a function prime_factors that takes a single argument N, and returns a list of all prime factors of N. The result doesn't have to be in any particular order. Add this function to your module's export-list.

4. Create a function is_square_multiple that takes a single argument N, and returns true if the argument is a multiple of some square, or false if it is not.

• Hint 1: A number is a multiple of a square if it has any prime-factors that appear more than once.
• Hint 2: You might find some of the functions in the lists and/or sets modules to be of use! The online erlang documentation is available here. For example, you might sort the list of prime-factors, then search the sorted list for the same prime-factor appearing twice in sequence.
5. Finally, create a function find_square_multiples(Count, MaxN). This function takes a count of how many square-multiples in a row there should be, and also a maximum value of where to stop searching.

• If the function finds a series of Count square-multiples in the range [2, MaxN], it should return the first number in the run.
• If the function doesn't find any series of Count square-multiples in this range, it should return the atom fail.

So, for example, you might have this interaction:

```    1> c(mobius.erl).
{ok,mobius}
2> mobius:find_square_multiples(3, 50).
48
3> mobius:find_square_multiples(3, 20).
fail
4>```

Note that the start of the run must be no larger than MaxN; the entire run itself may extend beyond MaxN.

This function should also be exported by your mobius module.

6. Once you have finished this function, find the first square-multiple runs of length 4, length 5, and length 6. You will need to choose a MaxN of 30000. Your program should definitely complete in under 1 minute; if it takes longer then you may have non-tail-recursive code in your implementation, and you need to fix this. (In fact, a good implementation shouldn't take very long to find the answers, but you will have up to a minute to compute the answer.)