1. Write a method omega with signature LongStream omega(int n) that takes in an int n and returns a IntStream containing the first n omega numbers. We use LongStream in order to work with large integer values.
The ith omega number is the number of distinct prime factors for the number i. The first 10 omega numbers are 0,1,1,1,1,2,1,1,1,2. The isPrime method is given below:
boolean isPrime(int n) { return IntStream .range(2, n)
.noneMatch(x -> n%x == 0);
}
2. Write a method that returns the first n Fibonacci numbers as a Stream<Integer>.
For instance, the first 10 Fibonacci numbers are 1,1,2,3,5,8,13,21,34,55.
Hint: Write an additional Pair class that keeps two items around in the stream
3. In this question, we shall attempt to parallelize the generation of the Fibonacci sequence. As an example, supose we are given the first k = 4 values of the sequence f1 to f4, i.e.
1,1,2,3
To generate the next k − 1 values, we observe the following:
f5
=
f3 + f4
=
1 · f3 + 1 · f4
=
f1 · f3 + f2 · f4
f6
=
f4 + f5
=
1 · f3 + 2 · f4
=
f2 · f3 + f3 · f4
f7
=
f5 + f6
=
2 · f3 + 3 · f4
=
f3 · f3 + f4 · f4
Notice that generating each of the terms f5 to f7 only depends on the terms of the given sequence. This actually means that generating the terms can now be done in parallel! In addition, repeated application of the above results in an exponential growth of the Fibonacci sequence.
You are now given the following program fragment:
BigInteger findFibTerm(int n) {
List<BigInteger> fibList = new ArrayList<>();
fibList.add(BigInteger.ONE); fibList.add(BigInteger.ONE);
1
while (fibList.size() < n) { generateFib(fibList);
}
return fibList.get(n-1);
}
(a) Using Java parallel streams, complete the generateFib method such that each method call takes in an initial sequence of k terms and fills it with an additional k − 1 terms. The findFibTerm method calls generateFib repeatedly until the nth term is generated and returned.
(b) Using the Instant and Duration classes, determine the time it takes the Fibonacci sequence of n = 50000. Compare the times for sequential and parallel generations.
