fib

#include <iostream>
#include "BigInt.hpp" // download from: https://faheel.github.io/BigInt/
#include <chrono>

using namespace std;

typedef BigInt bint;



class timer{
    std::chrono::time_point<std::chrono::high_resolution_clock> a,b;
public:
    void start(){a = std::chrono::high_resolution_clock::now();}
    void stop() {b = std::chrono::high_resolution_clock::now();}
    double value()
    {
        std::chrono::duration<double> elapsed_seconds = b-a;
        return elapsed_seconds.count();
    }
};


bint fib (uint64_t n){
    if (n==0) return 0;
    int shift =0;
    uint64_t nn=n;
    while (nn>1){
        shift++;
        nn/=2;
    }


    bint fk=1, fkp1=1; //F(k) and F(k+1) where k = n>>shift
    bint f2kp1, f2k;

    for (;shift>0; shift--){
        f2kp1 = fkp1*fkp1+fk*fk;
        f2k = 2*fkp1*fk-fk*fk;
        if ((n>>(shift-1))%2==0 ){
            fk = f2k;
            fkp1 = f2kp1;
        }else{
            fk = f2kp1;
            fkp1 = f2kp1+f2k;
        }
    }
    return fk;
}

void test (uint64_t j){

    timer t,t2;
    t.start();
    auto f = fib(j);
    t.stop();t2.start();
    string s = f.to_string();
    t2.stop();
    cout<<"fib("<< j<< ") " << s <<" number of digits: " <<s.length()<<endl;
    cout <<"calcualted in "<< t.value() <<" s + string created in "<<t2.value() << endl;
}

int main()
{
  test(10000);
  test(33300);
  return 0;
}