You are not logged in. Please login at www.codechef.com to post your questions!

×

Fastest Way to calculate Nth fibonacci number modulo M

2
3

1 ≤ N,M ≤ 1018 code using Fast Doubling

#include <map>
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MAXN 60 
#define MAXM 4
long long int M,N ; 
long long F[MAXN][MAXM],FB[MAXN+5];
void readint(long long &a)
{
register int c;
a = 0;
do c = getchar_unlocked(); while(c < '0');
do{
a = (a << 1) + (a << 3) + c - '0';
c = getchar_unlocked();
}while(c >= '0');
}
void printint(long long int a)
{
char s[21];
int t = -1;

do{
s[++t] = a % 10 + '0';
a /= 10;
}while(a > 0);

while(t >= 0)putchar_unlocked(s[t--]);
putchar_unlocked('\n');
}
long long int mulmod(long long int a,long long int b) {
   long double res = a;
   res *= b;
   long long int c = (long long)(res / M);
   a *= b;
   a -= c * M;
   a %= M;
   if (a < 0) a += M;
   return a;
}
long long int  f(long long int  n,int depth = 0 ) {
    if(n<=MAXN){
        return FB[n]%M ;
    }
    int val = n%4 ; 
    if (F[depth][val] != -1) 
        return F[depth][val];
    long long int  k=n >> 1;
    long long int a,b,c;    
    a = f(k,depth+1) ;
    b = f(k-1,depth+1) ;
    if (n%2==0) { 
        F[depth][val] = (mulmod(a,a) + mulmod(b,b));
    }else { 
        c = f(k+1,depth+1) ;        
        F[depth][val] = (mulmod(a,c) + mulmod(b,a));
    }
    if(F[depth][val] >= M)
        F[depth][val] -= M ;
    return F[depth][val] ;
}

int main(){
    int T = 63450 ;
    FB[0] = 1 ;
    FB[1] = 1 ;
    for(int i=2;i<=64;i++){
        FB[i] = FB[i-1] + FB[i-2] ;
    }
    while(T--){
        memset(F,-1,sizeof F) ;
        readint(N) ;
        readint(M) ;
        printint((N==0 ? 0 : f(N-1))) ;
    }   
    return 0 ; 
}

asked 25 Jan '15, 15:22

ma5termind's gravatar image

3★ma5termind
1.7k11530
accept rate: 11%

edited 27 Jan '15, 13:09

You can add related questions to it, I remember there was a question on spoj based on some GCD thing whose logic was just finding the n't fibonacci number. Range was large, don't remember the name or code of that.

(25 Jan '15, 17:38) damn_me3★

Hello frendz ..

code is updated and syncronized so that you can get AC on spoj with it .. it is able to answer 61100 test cases on a rough idea. We can do some optimisation and can take it to 62000 easily . suggest some optimisation .. i have one in my mind ..

(27 Jan '15, 11:21) ma5termind3★
1

Hey guys i have applied the optimisation and boom i am able to take it to 63450 from 61100 . Think of some more optimisations .

@i_am_what_i_am he was actually correct that this is not the fastest code for generating the answer but this may be the simplest code .

(27 Jan '15, 13:11) ma5termind3★

Also, I'd like to bring upon this method also:

MATRIX EXPONENTIATION: (n+1)th fibonacci number is obtained by multiplying the matrix M n times where M is a 2X2 matrix defined as:

M=  [1,1]
    [1,0]

M*Fk= Fk+1

The matrix obtained by multiplying this matrix M n times will give us the n+1th fibonacci number as the entro [0,0] (row=0 and colomn=0). Why such happens can be seen this way:

| 1   1 | x |  f(n)  | = | f(n+1) | // this will represent the current solution
| ----- |   | f(n-1) |   | f(n)   | 
 /|\             /|\
  |               |

M matrix Solution to the previous state

f(n+1) is f(n) + f(n-1) which can come if M[0][0]=1 and M0=1(do matrix multiplication and u'll get this). f(n) is possible if, M1[0]=1 and M1=0, that gives us the value of M[][].

Multiplying with M on both sides above, we get:

M x M x |  f(n)  | = M x | f(n+1) | = | f(n+2) |
        | f(n-1) |       |  f(n)  |   | f(n+1) |

Again multiplying repeatedly will gives us :

M^k x |  f(n)  | = | f(n+k) |
      | f(n-1) |   |f(n+k-1)|

From this, we see that a matrix of the first three fibonacci numbers, times a matrix of any three consecutive fibonacci numbers, equals the next. So we know that:

     n
[1 1]   =  [fib(n+1) fib(n)  ]
[1 0]      [fib(n)   fib(n-1)]

which makes the complexity of computation as O(logn) if computed efficiently. For code, you may like seeing this.

Also, wiki says a closed form solution of the same is :

The nth Fibonacci number is given by

       f(n) = Floor(phi^n / sqrt(5) + 1/2)
         where
       phi = (1 + sqrt(5)) / 2

Even this can be computed in O(logn) time. The result is deducible from the very same fact of the above exponentiation method. If the result of the matrix is calculating by finding eigen values, it'll come this only.

link

answered 25 Jan '15, 18:17

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

Is this the fastest? How many cases does your code pass here? http://www.spoj.com/ranks/FIB64/ I got 61400.

link

answered 25 Jan '15, 19:07

i_am_what_i_am's gravatar image

6★i_am_what_i_am
652
accept rate: 10%

1

Have not tried yet .. you can check if you want .. and do inform about the result here ..

(25 Jan '15, 19:20) ma5termind3★
1

how did u get 61400?,I got only 30k :/.

(25 Jan '15, 19:32) kislaya4★

WA on spoj... LOL Try it yourself!

(25 Jan '15, 19:33) i_am_what_i_am6★
1

@kislaya- Like in matrix exponentiation, we break n to n/2 size. Similarly there is a way to break it into n/3. So my code runs in log (base 3). Thats why its faster. But I wanted to know if anyone knows what algorithm passes 500000 test cases. 2 people have achieved that in the link.

(25 Jan '15, 19:38) i_am_what_i_am6★
1

change limit mentioned above from 55 to 60 or 65 you will get AC on spoj and also consider the case when N = 0 .. 60,000 are easily achievable using this code ..

(25 Jan '15, 20:14) ma5termind3★
2

@i_am_what_i_am

can you share your code. we are more happy in learning something new .. :D

(25 Jan '15, 20:17) ma5termind3★

Hmm.. Does anyone have any idea how people cam pass 5,00,000 cases? I have no idea..

(25 Jan '15, 20:18) i_am_what_i_am6★
1

also remove that printf statement .. to get it accepted on spoj ..

(25 Jan '15, 20:20) ma5termind3★
2

@i_am_what_i_am

Can you please share your code with us. we are more happy in learning some new stuff ..

(25 Jan '15, 20:21) ma5termind3★

@i_am_what_i_am,Please share your code :) :)

(26 Jan '15, 14:24) rudra_sarraf3★

@i_am_what_i_am you can try it now ..

(27 Jan '15, 11:21) ma5termind3★
showing 5 of 11 show all

@damn_me : thnx damn_me The method u have suggested is the fastest mehtod known uptill now for calculating fibonacci numbers.

link

answered 25 Jan '15, 18:23

saiavinashiitr's gravatar image

1★saiavinashiitr
904512
accept rate: 0%

1

Method suggested in the thread is even faster than Matrix Exponentiation .. FAST DOUBLING

(25 Jan '15, 18:26) ma5termind3★
1

Fast doubling is the fastest known method, although it is derived from the matrix exponentiation method but many redundant calculations are not there in fast doubling. And thus it differs from the matrix one by a significant constant factor. I mentioned there in the post along with because I myself learnt it the hard way the time I did :P

(25 Jan '15, 18:45) damn_me3★

@ma5termind I think its better if you change the tag of your thread, include fibonacci also. Search query of People unaware of the method will be "fibonacci", "large number" or similar. So, its just a suggestion.

(25 Jan '15, 18:48) damn_me3★

@damm_me sure i will ..

(25 Jan '15, 19:18) ma5termind3★

Thanks a lot.But pls pls explain a bit too, what u did with the "val" in F[depth][val]??? And in - "if (a < 0) a += M;return a;", when a is going to be negative? Thanks in advance.

link

answered 25 Jan '15, 21:36

shubham201's gravatar image

3★shubham201
513
accept rate: 8%

edited 25 Jan '15, 23:20

could anyone explain what is the logic behind the function long long int f(long long int n, int depth=0) and long long int mulmod(long long int a, long long int b) . Thankyou in advance.

link

answered 06 Sep '15, 00:33

suryavamsi's gravatar image

2★suryavamsi
212
accept rate: 0%

https://www.codechef.com/problems/CURR3
#include<bits stdc++.h="">
using namespace std;
#define ll long long 
#define m 1000000007
void multiply(ll f[][2],ll g[][2])
{
    ll a=(f[0][0]*g[0][0]+f[0][1]*g[1][0])%m;
    ll b=(f[0][0]*g[0][1]+f[0][1]*g[1][1])%m;
    ll c=(f[1][0]*g[0][0]+f[1][1]*g[1][0])%m;
    ll d=(f[1][0]*g[0][1]+f[1][1]*g[1][1])%m;

    f[0][0]=a;
    f[0][1]=b;
    f[1][0]=c;
    f[1][1]=d;
}
void power(ll f[2][2],ll n)
{
    ll g[2][2]={{1,1},{1,0}};
    if(n==0||n==1)
    return;
    power(f,n/2);
    multiply(f,f);

    if(n%2==1)
    multiply(f,g);
}
ll fib(ll n)
{
    ll f[2][2]={{1,1},{1,0}};
    if(n==0)
    return 0;
    power(f,n-1);
    return f[0][0]%m;
}

int main() {
    ll n;
    cin>>n;
        cout<
link

answered 11 Mar '17, 16:06

adhish_kapoor's gravatar image

3★adhish_kapoor
9048
accept rate: 9%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×619
×53
×35
×17
×8
×5
×4

question asked: 25 Jan '15, 15:22

question was seen: 11,427 times

last updated: 11 Mar '17, 16:06