This exam must be developed individually.
This problem is an adaptation of problem 303 Multiples with small digits from Project Euler.
For a positive integer n, define f(n) as the least positive multiple of n that, written in base 10, uses only digits that are less or equal to 2. Thus f(2)=2, f(3)=12, f(7)=21, f(42)=210, f(89)=1,121,222, f(108)=112,212, f(899)=222,222,012.
Find:
The correct answer is 59,522,298.
Write a Clojure function that allows you to compute this solution in parallel, using a computer system with a dual-core CPU or better. The name of the function must be multiples and it must be contained in a namespace called exam3 (thus, your source file should be called exam3.clj). The function should take as an argument the number of threads to use during the computation.
Usage examples:
(exam3/multiples 1) ⇒ 59522298 (exam3/multiples 2) ⇒ 59522298 ;;; Same result as above, except computed faster! ;;; Using all available CPU cores. (def n (.. Runtime getRuntime availableProcessors)) n ⇒ 4 (exam3/multiples n) ⇒ 59522298 ;;; Use the 'time' function to measure the execution speed. (time (exam3/multiples 1)) "Elapsed time: 5316.49139 msecs" ⇒ 59522298 (time (exam3/multiples 2)) "Elapsed time: 2998.792322 msecs" ⇒ 59522298 (time (exam3/multiples n)) "Elapsed time: 2437.281383 msecs" ⇒ 59522298
You may define any number of additional auxiliary functions. Just make sure every single function contains a doc-string explaining its purpose.
Avoid using functions that create huge lists. These functions usually don't perform well when running in multiple threads. This means that when doing repetitions you might be better off using loop/recur.
Run your functions multiple times and measure how long they take to execute for different number of threads.
The program source file must include at the top the author's personal information (name and student ID) within comments. For example:
;;;----------------------------------------------------
;;; ITESM CEM, November 12, 2012.
;;; Clojure Source File
;;; Activity: Third Quarter Term Exam
;;; (Multiples with small digits)
;;; Author: 1166611 Anthony Stark
;;;----------------------------------------------------
.
. (The rest of the program goes here)
.
Write a report of at least 200 words in which you describe how you solved the problem, the results of the time measurements and your conclusions. Include also at least one chart (bar chart, line chart, etc.) in which the speedup improvements can be clearly observed. The report must be presented as a PDF document called report.pdf.
Place both files (exam3.clj and report.pdf) in a tarball file called exam3.tgz. From a terminal, you can use the following command to create this file:
tar czf exam3.tgz exam3.clj report.pdf
Using the Online
Assignment Delivery System (SETA), deliver the file
exam3.tgz. No exams will be accepted through
e-mail or any other means.
Due date: Monday, November 12.
| 35% | The implementation gives the correct result. |
|---|---|
| 35% | The implementation produces an observable speedup (Sp = 1.2 or higher) when running the function with multiple threads in a multi-core system. |
| 20% | The written report contains all the requested elements. |
| 5% | Each function in the Clojure source file contains a short documentation string. |
| 5% | The source file contains within comments the authors' personal information. |
| DA | In case of plagiarism or any kind of fraud. |