Echo89

fib test

Sep 2nd, 2015
68
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream> // cout
  2. #include <cmath> // sqrt
  3. #include <chrono>    // steady_clock
  4. #include <sstream>   // istringstream
  5.  
  6. std::pair<int64_t, double> fib1(int64_t n) {
  7.     auto t1 = std::chrono::steady_clock::now();
  8.    
  9.     int64_t nth_fib =    (1 / std::sqrt(5)) *
  10.                         std::pow((1 + std::sqrt(5)) / 2, n) -
  11.                         (1 / std::sqrt(5)) *
  12.                         std::pow((1 - std::sqrt(5)) / 2, n);
  13.  
  14.     auto t2 = std::chrono::steady_clock::now();
  15.    
  16.     double seconds = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1).count();
  17.    
  18.     return {nth_fib, seconds};
  19. }
  20.  
  21. std::pair<int64_t, double> fib2(int64_t n) {
  22.     auto t1 = std::chrono::steady_clock::now();
  23.    
  24.     int64_t a = 0, b = 1, c = 1;
  25.    
  26.     for(int64_t i = 1; i < n; i++) {
  27.         c = a + b;
  28.         a = b;
  29.         b = c;
  30.     }
  31.    
  32.     auto t2 = std::chrono::steady_clock::now();
  33.    
  34.     double seconds = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1).count();
  35.    
  36.     return {c, seconds};
  37. }
  38.  
  39. int main(int argc, const char * argv[]) {
  40.     if(argc == 1) {
  41.         std::cout << "Please specify a valid number to test." << "\n";
  42.        
  43.         return 1;
  44.     }
  45.    
  46.     int64_t n;
  47.     if (!(std::istringstream(argv[1]) >> n)) {
  48.         std::cout << "Please specify a valid number to test." << "\n";
  49.         return 1;
  50.     }
  51.    
  52.     int64_t nth_fib1, nth_fib2;
  53.     double seconds1, seconds2;
  54.    
  55.     std::tie(nth_fib1, seconds1) = fib1(n);
  56.     std::tie(nth_fib2, seconds2) = fib2(n);
  57.    
  58.     std::cout << std::fixed << "Method 1: " << nth_fib1 << ", took " << seconds1 << "s\n";
  59.     std::cout << std::fixed << "Method 2: " << nth_fib2 << ", took " << seconds2 << "s\n";
  60.    
  61.     return 0;
  62. }
RAW Paste Data