The project will be an exercise in concurrentprogramming and will require you to parallelize the computation ofsum of Euler totient computations over a range of integer values.The Euler totient function computes the number of integers that arecoprime (⊥) to a given integer n. The totient function is definedas follows:
- Must Be Done In Java The Project Will Be An Exercise In Concurrent Programming And Will Require You To Parallelize The C 1 (2.84 KiB) Viewed 45 times
PROVIDE A CONCURRENT IMPLEMENTATION OF THE CODE INLISTING 1 USING THREADS IN JAVA. NOTE THAT YOU ARE NOT ALLOWED TOCHANGE THE SUM OF EULER TOTIENT ALGORITHM SUCH THAT IT BECOMES MOREEFFICIENT.. A deliberately inefficient sequentialimplementation has been provided so that any speed up via theemployment of threads is not imperceptible. You will be required tostudy the implementation of the algorithm and identify whichpart(s) can be executed concurrently such that the overall resultis correct but a faster execution is realized. Bonus points will beawarded for any implementation that tries to optimize how data isshared among multiple threads for a faster runtime.
To establish a baseline of performance, you are required toexecute the sequential implementation using the followinginputs:
• Sum of totients between 1 and 10000
• Sum of totients between 1 and 20000
• Sum of totients between 1 and 50000
For larger ranges the runtime of the sequential implementationwill increase; depending on the speed of your CPU, execution maytake several minutes.
- Must Be Done In Java The Project Will Be An Exercise In Concurrent Programming And Will Require You To Parallelize The C 2 (62.47 KiB) Viewed 45 times
- Must Be Done In Java The Project Will Be An Exercise In Concurrent Programming And Will Require You To Parallelize The C 3 (43.58 KiB) Viewed 45 times
You are required to submit a source code in thestructure outlined below.
[{u+w\u>w/N⇒ w} = (u)
Two numbers m and n are said to be relativey prime, if the only integer number that divides them both is 1. It is therefore necessary to establish that their greatest common divisor (ged) is 1, i.e. mln = gcd(m, n) = 1. The program should thus compute -1 (n). The Java code in listing 1 is a direct sequential implementation of the above specification and is provided as a starting point for your concurrent implementation. So, if the program is executed as follows: TotientRange 1 100, its output should be 3044.
1 2 3 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.lang. System; public class TotientRange{ long hef (long x, long y){ long t; } } while (y != 0) { t = x x % y; x = y; y = t; boolean relprime (long x, long y) { return hef(x, y) == 1; } } return x; long euler (long n) { long length, i; } length = 0; for (i = 1; i <= n; i++) if (relprime (n, i)) length++; return length; long sumTotient (long lower, long upper) { long sum, i; sum = 0; for (i = lower; i <= upper; i++) sum = sum + euler(i); return sum; public static void main(String[] args) { long lower = 0; long upper = 0; try{ lower = Long.parseLong(args [0]);
45 46 47 48 49 50 51 52 53 55 56 57 58 59 60 } } upper Long.parseLong(args [1]); }catch(Exception e) { } System.out.println("Error (lower: " + lower + return; 11 , upper: + upper + ")"); TotientRange tr = new TotientRange(); long startTime = System.nanoTime(); System.out.println("Totient Sum: " + tr.sumTotient (lower, upper)); long endTime = System.nanoTime (); long duration = ((endTime - startTime) / 1000000) / 1000; System.out.println("Time Taken: " + duration + " seconds"); Listing 1: Implementation of Euler Specification