CS245

Overview

In this assignment you will work with a partner. The task is to produce two programs that do exactly the same thing (in slightly different ways.) One version in Go and the other using Elixir. Then, based on your experience with the programs answer the questions posed at the end of the assignment. I imagine that you will do the following:

Find a partner
With your partner, sketch out program flow for the Go and Elixir programs.
Split work, one person do the program in Go, the other in Elixir (Alternately you could use paired programming. If you do this, I highly encourage you to switch off the person who is typing and the person who is thinking / researching.)
Answer the summary questions.

You are not required to work with a partner. If you do not, then you must write the program in Elixir. There is a special set of summary questions a for people working solo. You should answer only those questions.

Perfect numbers

According to Wikipedia "in number theory, a perfect number is a positive integer that is equal to the sum of its positive divisors, excluding the number itself. For instance, 6 has divisors 1, 2 and 3 (excluding itself), and 1 + 2 + 3 = 6, so 6 is a perfect number. ".

Perfect numbers are rare. There are only 51 known. They get big fast ... The first five are: 6, 28, 496, 8128 and 33550336. There are no known odd perfect numbers; it has not been proven that odd perfect numbers do not exist. Slightly less rare are numbers that are close to perfect.

Task 0

Find a partner.

Send the names of the two people in your group to gtowell@brynmawr.edu.

Task 1

Write programs in Elixir and Go that run with multiple threads to find perfect, and close to perfect, numbers. Your program need not be efficient (a brute force factorer is fine. That is, just get remainder of the target number with respect to every number less that that square root of the target. If the remainder is 0 it is a factor.). Since it is known that the smallest possible odd perfect number is greater than 10¹⁵⁰⁰ your programs may skip odd numbers. There may be odd numbers that are close to perfect. It is OK to miss these.

Program Requirements

Your programs should take one argument from the command line, namely the maximum number to consider in your search for perfect numbers
You programs should, in addition to finding perfect numbers, find all numbers such that they are within 3 of being perfect. (That is, the absolute value of sum of the factors of a number minus the number itself should be less than or equal to 3.
You programs must be multi-threaded. You may do something very simple here. For instance, have one thread find perfect, and close-to-perfect numbers in the range 1-max/100, another thread in the range max/100+1..2*max/100, ...
Your program must start at least 100 meaningful threads.
Your Go program should use shared memory for communication between the threads.
Your programs should never have more than 40 running threads.
Your Elixir program should use message passing for thread communications

After finishing searching all numbers for perfection (up to the given max) you program should print out information like:

Perfect and near perfect (within 6) numbers below 100000
(Only even numbers considered)
    -6 ---> [592, 52]
    -5 ---> []
    -4 ---> [18632, 8384, 2144, 884, 152, 110, 44, 14]
    -3 ---> []
    -2 ---> [32896, 136, 10]
    -1 ---> [8192, 32768, 2048, 512, 128, 32, 8, 2]
    0 ---> [8128, 496, 28, 6]
    1 ---> [4]
    2 ---> [1952, 650, 464, 104, 20]
    3 ---> [18, 16]
    4 ---> [32128, 5830, 4030, 1888, 88, 70, 12]
    5 ---> []
    6 ---> []

If any of your Elixir functions are recursive they must be tail recursive.
Use the UNIX time function to determine the speedup from parallelization for both your Go and Elixir programs. This is very easy to use, just stick the word "time" in front of your program. For instance:
```
    time elixir perfect.ex > perr.out
    real    1466m55.366s
    user    10852m14.119s
    sys     5m49.169s    
```
This shows that my program used 10852 CPU minutes in 1466 clock minutes. That is a speedup of about 7.4 times (on an 8 core machine). Report your speedup(s) in your readme file for a run finding perfect numbers less than 1,000,000.
Show the output of your program for finding perfect numbers of less than 1,000,000 in the Readme file.
Do a multi-hour test of you perfect number finder on a lab machine. Do it overnight. Penalties will be assessed for being a bad sharer. Show the output of your programs on a multi-hour run. Use the UNIX "time" function here also. Put these results in your readme also.

Questions

Once you complete your programs, write short answers to the following questions. Please note that I am often asking you for opinions; so correctness is not an issue. Rather I am looking for well-thought statements based on you experience with writing these programs. Also, in all cases the portion of the response that address why is far more important than the part that address what. (For instance, suppose each response is worth 10 points, then what is worth no more than 1 or 2 points, why no less than 8 or 9.)

Questions for people who worked in Pairs

Overall, which version of the was easier / harder to write? why? (Try to correct for exogenous factors like "We wrote the Go version first".)
What about each language helped / hindered with task? This is not about functional vs imperative styles, but features of the language itself. Explain.
Did functional programming make the task easier or harder? Why?
Code readability / modifiability. Suppose in the next assignment you needed to adapt the program you wrote here. (For instance to find S-perfect numbers (look up the definition).) Which version would you think would be easier to adapt? Why?
Did you prefer message passing or shared memory for communications. Why?

Questions for people who worked Individually

What features of the language made it particularly easy or hard to write this program. Explain
Explain why you must use massage passing to coordinate threas in Elixir.
Code readability / modifiability. Suppose in the next assignment you needed to adapt the program you wrote here. (For instance to find S-perfect numbers (look up the definition).) Which version would you think would be easier to adapt? Why?

Electronic Submissions

Your submission will be handed in using the submit script.

If you write your program on computers other than those in the lab, be aware that your program will be graded based on how it runs on the department’s Linux server, not how it runs on your computer. The most likely problem is not submitting everything or hard coding file locations that are not correct on the Linux servers.

The submission should include the following items:

README:: This file should follow the format of this sample README

Names of both people in a group. You need only submit once.
Source files: All of them (you might have only one)
Data files used:: Be sure to include any non-standard data files uses. (Rare)
DO NOT INCLUDE:: Data files that are read from the class site. Do include any of your own data files.

Again: Once you have everything you want to submit in the a5 directory within /home/YOU/cs245/

Go to the directory /home/YOU/cs245
Enter /home/gtowell/bin/submit -c 245 -p 5 -d a5

If this worked you will get a message with the word "success". If you cannot achieve success and the deadline is approaching, send me email. We can set up a meeting to work out your problems. The email will establish that you intended to submit. Once you send the email, do not change the files that you were trying to submit.