// g++ fibonacci-midiendo-tiempos.cpp -lrt -O3 && ./a.out  | tee fibonacci-midiendo-tiempos.resultados

#include <iostream>

#include <iomanip> // setprecision
#include <ctime>   // clock_gettime

using namespace std;

double segundosDiferencia(timespec inicio, timespec fin) {
   const double nano = 1e9;
   return ( (fin.tv_sec + fin.tv_nsec / nano) - (inicio.tv_sec + inicio.tv_nsec / nano) );
}

long long fibonacciRecursiva(int n) {
   if (n <= 1) return n;
   return fibonacciRecursiva(n-1) + fibonacciRecursiva(n-2);
}

long long fibonacciIterativa(int n) {
   long long penultimo = 0, ultimo = 1, fibonacci = n;
   for (int i = 2; i <= n; i++) {
      fibonacci = ultimo + penultimo;
      penultimo = ultimo;
      ultimo = fibonacci;
   }
   return fibonacci;
}

int main () {
   int dato;
   long long resultado1, resultado2;
   timespec tiempoInicial, tiempoFinal;

   cout << fixed << setprecision(10); // Para mostrar los tiempos con 10 cifras decimales

   for (dato = 0; dato <= 50; dato++) {

      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
      resultado1 = fibonacciRecursiva(dato);
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
      double tiempoSolucionRecursiva = segundosDiferencia(tiempoInicial, tiempoFinal);

      //      cout << "Fibonacci(" << dato << ") = " << resultado1 << endl;

      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoInicial);
      resultado2 = fibonacciIterativa(dato);
      clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &tiempoFinal);
      double tiempoSolucionIterativa = segundosDiferencia(tiempoInicial, tiempoFinal);

      //      cout << "Fibonacci(" << dato << ") = " << resultado2 << endl;

      if (resultado1 != resultado2) // Esto no va a pasar pero puede
	 // servir para que el compilador al optimizar no elimine las
	 // llamadas a funciones cuyo resultado no se utiliza
	 cout << "ERROR" << endl;
      else
	 cout << dato << "\t" << tiempoSolucionIterativa << "\t" << tiempoSolucionRecursiva << endl;

   }

}