#include <iostream>
#include <cassert>
#include <cstdint>

// In a previous exercise, you may have noticed
// that calculating Fibonacci numbers recursively
// is very slow. Really, really slow.
//
// The straightforward recursive implementation
// repeatedly calculates the same Fibonacci
// numbers, resulting in an exponential running
// time.
//
// You will implement three more efficient
// Fibonacci functions.
//
// We use std::uint64_t for the Fibonacci values,
// so we can calculate F(93) without overflow.
// All functions require n <= 93.
//
// A. Using a dynamically allocated array:
//
//    For n = 0, 1, or 2, simply return
//    0, 1, or 1, respectively.
//
//    Otherwise, allocate an array of
//    capacity n + 1 and initialize its
//    first three entries to 0, 1, and 1.
//
//    Use a loop to fill the remaining entries.
//    Each entry is the sum of the two
//    preceding entries.
//
//    Return the final entry and release
//    the dynamically allocated array.
//
//    We call this the "memo" version, although
//    the technique is more precisely known
//    as bottom-up dynamic programming.
//
// B. Returning a dynamically allocated array:
//
//    Allocate an array of capacity n + 1.
//
//    Initialize the entries that exist:
//
//        n = 0: {0}
//        n = 1: {0, 1}
//        n = 2: {0, 1, 1}
//
//    For n > 2, use a loop to fill the
//    remaining entries as in Function A.
//
//    Return the address of the array.
//
//    The calling function is responsible
//    for releasing the array using delete[].
//
// C. Using two local variables:
//
//    For n = 0 or 1, return n.
//
//    Otherwise, initialize two variables:
//
//        older{ 0 }
//        newer{ 1 }
//
//    Loop from k = 2 through n.
//
//    During each iteration:
//
//      1. Store the current value of newer
//         in a temporary variable.
//      2. Add older to newer.
//      3. Assign the temporary value to older.
//
//    Return newer.
//
//    This version requires only a constant
//    amount of additional memory.

// Function declarations
int main();

std::uint64_t fibonacci_rec(
    unsigned long const n
);

std::uint64_t fibonacci_memo(
    unsigned long const n
);

std::uint64_t *fibonacci_array(
    unsigned long const n
);

std::uint64_t fibonacci_fast(
    unsigned long const n
);

// Function definitions
int main() {
    std::cout << "Slow: f(43) = "
              << fibonacci_rec( 43 ) << std::endl;

    std::cout << "Very slow: f(45) = "
              << fibonacci_rec( 45 ) << std::endl;

    std::cout << std::endl;

    for ( unsigned long n{ 80 }; n <= 93; ++n ) {
        std::cout << "Array: f(" << n << ") = "
                  << fibonacci_memo( n ) << std::endl;
    }

    std::cout << std::endl;

    std::uint64_t *a_fibonacci{
        fibonacci_array( 93 )
    };

    assert( a_fibonacci != nullptr );

    for ( unsigned long n{ 80 }; n <= 93; ++n ) {
        std::cout << "Returned array: f(" << n
                  << ") = " << a_fibonacci[n]
                  << std::endl;
    }

    std::cout << std::endl;

    delete[] a_fibonacci;
    a_fibonacci = nullptr;

    for ( unsigned long n{ 80 }; n <= 93; ++n ) {
        std::cout << "Fast: f(" << n << ") = "
                  << fibonacci_fast( n ) << std::endl;
    }

    // Test the base cases.
    assert( fibonacci_memo( 0 ) == 0 );
    assert( fibonacci_memo( 1 ) == 1 );
    assert( fibonacci_memo( 2 ) == 1 );

    assert( fibonacci_fast( 0 ) == 0 );
    assert( fibonacci_fast( 1 ) == 1 );
    assert( fibonacci_fast( 2 ) == 1 );

    // Test the largest supported Fibonacci number.
    assert(
        fibonacci_memo( 93 )
        == 12200160415121876738ULL
    );

    assert(
        fibonacci_fast( 93 )
        == 12200160415121876738ULL
    );

    // Verify that all three new implementations
    // agree for every supported argument.
    std::uint64_t *all_values{
        fibonacci_array( 93 )
    };

    assert( all_values != nullptr );

    for ( unsigned long n{ 0 }; n <= 93; ++n ) {
        assert( fibonacci_memo( n ) == all_values[n] );
        assert( fibonacci_fast( n ) == all_values[n] );
    }

    delete[] all_values;
    all_values = nullptr;

    return 0;
}

// The original recursive implementation.
// This is provided for comparison.

std::uint64_t fibonacci_rec(
    unsigned long const n
) {
    assert( n <= 93 );

    if ( n == 0 ) {
        return 0;
    } else if ( n <= 2 ) {
        return 1;
    } else {
        return fibonacci_rec( n - 1 )
             + fibonacci_rec( n - 2 );
    }
}

std::uint64_t fibonacci_memo(
    unsigned long const n
) {
    assert( n <= 93 );

    // Your implementation goes here.

    return 0;
}

std::uint64_t *fibonacci_array(
    unsigned long const n
) {
    assert( n <= 93 );

    // Your implementation goes here.

    return nullptr;
}

std::uint64_t fibonacci_fast(
    unsigned long const n
) {
    assert( n <= 93 );

    // Your implementation goes here.

    return 0;
}









































// Here is one solution:

/*
std::uint64_t fibonacci_memo(
    unsigned long const n
) {
    assert( n <= 93 );

    if ( n <= 1 ) {
        return n;
    } else if ( n == 2 ) {
        return 1;
    }

    // Allocate the working array.
    std::uint64_t *values{
        new std::uint64_t[n + 1]{}
    };

    values[0] = 0;
    values[1] = 1;
    values[2] = 1;

    for ( unsigned long k{ 3 }; k <= n; ++k ) {
        values[k] = values[k - 1] + values[k - 2];
    }

    // Save the result before releasing
    // the dynamically allocated array.
    std::uint64_t const result{ values[n] };

    delete[] values;
    values = nullptr;

    return result;
}

std::uint64_t *fibonacci_array(
    unsigned long const n
) {
    assert( n <= 93 );

    std::uint64_t *values{
        new std::uint64_t[n + 1]{}
    };

    values[0] = 0;

    if ( n == 0 ) {
        return values;
    }

    values[1] = 1;

    if ( n == 1 ) {
        return values;
    }

    values[2] = 1;

    for ( unsigned long k{ 3 }; k <= n; ++k ) {
        values[k] = values[k - 1] + values[k - 2];
    }

    return values;
}

std::uint64_t fibonacci_fast(
    unsigned long const n
) {
    assert( n <= 93 );

    if ( n <= 1 ) {
        return n;
    }

    std::uint64_t older{ 0 };
    std::uint64_t newer{ 1 };

    for ( unsigned long k{ 2 }; k <= n; ++k ) {
        std::uint64_t const tmp{ newer };

        newer += older;
        older = tmp;
    }

    return newer;
}
*/

// QUESTION
//
// Why does the following loop produce
// exactly the same result without using
// a temporary variable?
//
//     for ( unsigned long k{ 2 }; k <= n; ++k ) {
//         newer += older;
//         older = newer - older;
//     }
//
// Explain why both versions maintain the
// same values of older and newer after
// every iteration.