bartekltg

fib

Oct 22nd, 2021
857
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <utility>
  3. #include <tuple>
  4.  
  5. using namespace std;
  6.  
  7. pair<uint64_t, uint64_t> fib_intr( const uint64_t n, const uint64_t M){
  8. // returns {fib_n, fib_{n-1}}
  9.     if (n==1)
  10.         return make_pair(1,0);
  11.     else{
  12.         uint64_t Fk, Fkm1;
  13.         tie(Fk, Fkm1) = fib_intr( n/2, M);
  14.         uint64_t F2km1 = (Fk * Fk + Fkm1*Fkm1)%M;
  15.         uint64_t F2k = (Fk*(Fk + 2*Fkm1))%M;
  16.         if (n%2==0) //n==2k
  17.             return make_pair(F2k,F2km1);
  18.         else //n==2k+1
  19.             return make_pair((F2km1 + F2k)%M, F2k);
  20.     }
  21. }
  22.  
  23. uint64_t fib( const uint64_t n, const uint64_t M){
  24.     if (n==0)
  25.         return 0;
  26.     else
  27.         return fib_intr(n,M).first;
  28. }
  29.  
  30.  
  31.  
  32.  
  33. int main(int argc, char *argv[]){
  34.     const uint64_t M = 1000000000;
  35.     uint64_t fn=0, fnm1=1;
  36.     for (uint64_t i=0; i<50; i++ ){
  37.         cout<<i<<": "<<fib(i,M)<<" "<<fn<<"\n";
  38.         swap(fn, fnm1);
  39.         fn = (fn+fnm1)%M;
  40.     }
  41.     return 0;
  42. }
  43.  
RAW Paste Data