Advertisement
bartekltg

fib

Feb 27th, 2024
857
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.42 KB | None | 0 0
  1. #include <iostream>
  2. #include "BigInt.hpp" // download from: https://faheel.github.io/BigInt/
  3. #include <chrono>
  4.  
  5. using namespace std;
  6.  
  7. typedef BigInt bint;
  8.  
  9.  
  10.  
  11. class timer{
  12.     std::chrono::time_point<std::chrono::high_resolution_clock> a,b;
  13. public:
  14.     void start(){a = std::chrono::high_resolution_clock::now();}
  15.     void stop() {b = std::chrono::high_resolution_clock::now();}
  16.     double value()
  17.     {
  18.         std::chrono::duration<double> elapsed_seconds = b-a;
  19.         return elapsed_seconds.count();
  20.     }
  21. };
  22.  
  23.  
  24. bint fib (uint64_t n){
  25.     if (n==0) return 0;
  26.     int shift =0;
  27.     uint64_t nn=n;
  28.     while (nn>1){
  29.         shift++;
  30.         nn/=2;
  31.     }
  32.  
  33.  
  34.     bint fk=1, fkp1=1; //F(k) and F(k+1) where k = n>>shift
  35.     bint f2kp1, f2k;
  36.  
  37.     for (;shift>0; shift--){
  38.         f2kp1 = fkp1*fkp1+fk*fk;
  39.         f2k = 2*fkp1*fk-fk*fk;
  40.         if ((n>>(shift-1))%2==0 ){
  41.             fk = f2k;
  42.             fkp1 = f2kp1;
  43.         }else{
  44.             fk = f2kp1;
  45.             fkp1 = f2kp1+f2k;
  46.         }
  47.     }
  48.     return fk;
  49. }
  50.  
  51. void test (uint64_t j){
  52.  
  53.     timer t,t2;
  54.     t.start();
  55.     auto f = fib(j);
  56.     t.stop();t2.start();
  57.     string s = f.to_string();
  58.     t2.stop();
  59.     cout<<"fib("<< j<< ") " << s <<" number of digits: " <<s.length()<<endl;
  60.     cout <<"calcualted in "<< t.value() <<" s + string created in "<<t2.value() << endl;
  61. }
  62.  
  63. int main()
  64. {
  65.   test(10000);
  66.   test(33300);
  67.   return 0;
  68. }
  69.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement