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.
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):
(This is how the Fibonacci sequence is defined on both Mathworld and Wikipedia.)
Create a module named "fib", in the file "fib.erl".
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.
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.)
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.
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".
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:
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.
Create a module named "mobius", in the file "mobius.erl".
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.
Add is_prime to your module's export-list, and test it to make sure it works properly.
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.
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.
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.
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.
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.)
Put your results at the end of your answers.txt file from the first part.
And that's it. Submit your work on csman for grading!