Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <chrono>
- #include <boost/multiprecision/gmp.hpp>
- using namespace std;
- typedef boost::multiprecision::mpz_int 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.str();
- 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(30000000);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement