Consider the following program that profiles the performance of a function summing a Fibonacci series: #include #include #include long fib_sum(size_t n) { u // TODO: Adapt code from Exercise 12.1...

Consider the following program that profiles the performance of a function summing a Fibonacci series: #include #include #include long fib_sum(size_t n) { u // TODO: Adapt code from Exercise 12.1 return 0; } long random() { v static std::mt19937_64 mt_engine{ 102787 }; static std::uniform_int_distribution int_d{ 1000, 2000 }; return int_d(mt_engine); } struct Stopwatch { w Stopwatch(std::chrono::nanoseconds& result) : result{ result }, start{ std::chrono::system_clock::now() } { } ~Stopwatch() { result = std::chrono::system_clock::now() - start; } private: std::chrono::nanoseconds& result; const std::chrono::time_point start; }; long cached_fib_sum(const size_t& n) { x static std::map cache; // TODO: Implement me return 0; } int main() { size_t samples{ 1'000'000 }; std::chrono::nanoseconds elapsed; { Stopwatch stopwatch{elapsed}; volatile double answer; while(samples--) { answer = fib_sum(random()); y //answer = cached_fib_sum(random()); z } } printf("Elapsed: %g s.\n", elapsed.count() / 1'000'000'000.); { } This program contains a computationally intensive function fib_sum u that computes the sum of a Fibonacci series with a given length. Adapt your code from Exercise 13-1 by (a) generating the appropriate vector and (b) summing over the result with a range-based for loop. The random function v returns a random number between 1,000 and 2,000, and the Stopwatch class w adopted from Listing 12-25 in Chapter 12 helps you determine elapsed time. In the program’s main, you perform a million evaluations of the fib_sum function using random input y. You time how long this takes and print the result before exiting the program {. Compile the program and run it a few times to get an idea of how long your program takes to run. (This is called a baseline .) 13-6. Next, comment out y and uncomment z. Implement the function cached _fib_sum x so you first check whether you’ve computed fib_sum for the given length yet. (Treat the length n as a key into the cache.) If the key is present in the cache, simply return the result. If the key isn’t present, compute the correct answer with fib_sum, store the new key-value entry into cache, and return the result. Run the program again. Is it faster? Try unordered_map instead of map. Could you use a vector instead? How fast can you get the program to run?