Is there any formula to calculate nth fibonacci number ?

general
, ,
1

Suppose we are given, a(0)=x ; a(1)=y

and the relation, a[i]=a[i-1]+a[i-2]

and , we are asked to calculate a(n) , how to calculate it if n is as big as 10^9 ?

Thanks ! :slight_smile:

1 Like
2

I have found a formula on GeeksForGeeks site but since it involves floating operation it may produce some wrong results::

Fn = {[(1 + √5)/2] ^ n - [(1 - √5)/2]^n} / √5

Edit: This method will work fine till n < 80, after that it produces wrong results. I don’t think any formula exists for n as large as 1e9;

See this Article

1 Like
3

Suppose we want to solve f(n) = f(n-1) + f(n-2) + 3*n.

By @aryanc403 - Answer hidden.

1 Like
4

Please refrain from answering the second part of question ( solving f(n)=f(n-1)+f(n-2)+3*n ) as it is from an ongoing contest on hackerearth…

2 Likes
5

@aryanc403 , at that time , I was a newbie so I by-mistakely asked the question, but deleted it in just few minutes, I didn’t even got the answer to my query so don’t worry .
About this question , it was just to get some general knowledge about fibonacci numbers and their computation , I really have no idea with which ongoing contest does this question match (the most basic query) but I will figure it out myself, don’t bother yourselves :slight_smile:

By @aryanc403 - Link Hidden

So to satisfy my curiosity, I asked it here. Sorry for such a big mistake.

1 Like
7

private static long matrixExponential(long n, long x, long y) {
long[][] fib = {{1,1},{1,0}};
long[][] result = {{1,0}, {0,1}};
n --;
while (n != 0) {
if((n & 1) != 0)
result = matrixMultiply(result,fib);
n >>= 1;
fib = matrixMultiply(fib, fib);
}

        return result[1][0] * b + result[1][1] * a;
    }

    private static long[][] matrixMultiply(long[][] mat1, long[][] mat2) {
        long res[][] = new long[2][2];
        res[0][0] = mat1[0][0] * mat2[0][0]  + mat1[0][1] * mat2[1][0];
        res[0][1] = mat1[0][0] * mat2[0][1]+ mat1[0][1] * mat2[1][1];
        res[1][0] = mat1[1][0] * mat2[0][0]  + mat1[1][1] * mat2[1][0];
        res[1][1] = mat1[1][0] * mat2[0][1]  + mat1[1][1] * mat2[1][1];
        return res;
    }

Use matrix exponential to calculate original nth fibonacci number.

$
\begin{pmatrix}
f(n + 1) & f(n) \
f(n) & f(n - 1)
\end{pmatrix}^n
\

\
\begin{pmatrix}
1 & 1 \
1 & 0
\end{pmatrix}^n$

Then multiply the submatrix

\begin{pmatrix} f(n) & f(n-1) \end{pmatrix} \times \begin{pmatrix} y\\ x \end{pmatrix}

The answer obtained is your n modified fibonnaci number with f(0) = x and f(1) = y
Above is the code implementation in java.

8

Please do some research before asking questions :confused:

1 Like
9

Thanks bro :slight_smile:

10

Use Matrix Exponentiation to calculate it in log(N) time,it will be helpful.
:slight_smile:

1 Like
12

I finally got the answer by myself .LOL.

13

@aryanc403 here :

14

nope, we can’t, because if we reduce it to a 3X3 matrix, then the recurrence relation won’t hold anymore :slight_smile:

15

but, its awesome ! :slight_smile: