cppadvanced15 minutes

Build a High-Performance Memoized Fibonacci Function Using C++ Templates

Create an advanced C++ function that computes Fibonacci numbers efficiently using both memoization and template metaprogramming techniques to optimize compile-time and run-time performance.

Challenge prompt

Write a function `constexpr unsigned long long memoizedFibonacci(unsigned int n)` that calculates the nth Fibonacci number. The function should use memoization to cache previously computed results for run-time calls and also utilize template metaprogramming to enable compile-time computation for constant expressions where possible. You must ensure the function is safe for large inputs (up to 93) without integer overflow in unsigned long long. Avoid redundant calculations and optimize both compile-time and run-time efficiency.

Guidance

• Design a helper structure using templates to compute Fibonacci numbers at compile-time for constant values of n.
• Implement memoization using a static cache or a suitable in-function mechanism to speed up run-time calls.
• Ensure your solution handles both compile-time (`constexpr`) contexts and run-time calls seamlessly.
• Consider using constexpr if and inline static variables for caching in C++17 and later.

Hints

• Use template specialization to define base cases for Fibonacci (e.g., for 0 and 1).
• Static arrays or maps can hold cached values for run-time memoization.
• Leveraging constexpr functions with inline variables allows cache sharing across calls.

Starter code

constexpr unsigned long long compileTimeFib(unsigned int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return compileTimeFib(n - 1) + compileTimeFib(n - 2);
}

unsigned long long memoizedFibonacci(unsigned int n) {
    // TODO: Implement memoized Fibonacci function
    return 0;
}

Expected output

memoizedFibonacci(10) == 55 memoizedFibonacci(40) == 102334155 constexpr auto val = memoizedFibonacci(20); // val == 6765 (computed at compile-time if possible)

Core concepts

memoizationtemplate metaprogrammingconstexpr functionsoptimization

Challenge a Friend

Send this duel to someone else and see if they can solve it.