// fibo2.cpp
// Glenn G. Chappell
// 30 Sep 2009
//
// For CS 311 Fall 2009
// Computing Fibonacci Numbers
// Version #2: Iterative

#include <iostream>
using std::cout;
using std::endl;
using std::cin;


// Define numeric type for holding a (large?) Fibonacci number
typedef long long bignum;
// NOTE: (long long) is not a built-in type in ANSI-1998 C++.
// Use "long" above to make this program ANSI-1998 compliant.
// (And probably reduce the upper limit of the loop in function main.)

// fibo
// Given n, returns F(n) (the nth Fibonacci number).
// F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2) + F(n-1).
// Pre:
//     n >= 0.
//     F(n) is a valid bignum value.
// Notes:
//     If bignum is 32-bit signed integer,
//      then preconditions hold for 0 <= n <= 46.
//     If bignum is 64-bit signed integer,
//      then preconditions hold for 0 <= n <= 92.
// Post:
//     Return value is F(n).
// Does not throw.
bignum fibo(int n)
{
    // Two variables to hold consecutive Fibonacci numbers:
    //  the "previous" and "current" ones.
    bignum prev = bignum(1);
    bignum curr = bignum(0);

    // Invariant:
    //     prev == F(-1) == 1
    //     curr == F(0) == 0

    for (int k = 0; k < n; ++k)
    {
        // Here we slide prev & curr to the right

        // Loop invariant:
        //     prev == F(k-1)
        //     curr == F(k)

        bignum next = prev + curr;  // the next Fibonacci number after curr
        prev = curr;
        curr = next;

        // Loop invariant:
        //     prev == F(k)
        //     curr == F(k+1)
    }

    // Invariant:
    //     curr == F(n)

    return curr;
}


int main()
{
    cout << "Fibonacci Numbers" << endl;
    cout << endl;
    for (int i = 0; i <= 92; ++i)
    {
        cout << i << ": " << fibo(i) << endl;
    }
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}