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

and the relation, a*=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 !

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

and the relation, a*=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 !

1 Like

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;

1 Like

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

We could try to set up a matrix M to give

\left(\begin{matrix} f(n) \\ f(n-1) \\ n \\ 1 \end{matrix}\right) = \left(\begin{matrix} . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} \right) \left( \begin{matrix} f(n-1) \\ f(n-2) \\ n-1 \\ 1 \end{matrix} \right)

Then we can fill in the values. giving

M = \left( \begin{matrix} 1 & 1 & 3 & 3 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{matrix} \right)

and

\left(\begin{matrix} f(k+1) \\ f(k) \\ k+1 \\ 1 \end{matrix}\right) = M^{k} \left(\begin{matrix} f(1) \\ f(0) \\ 1 \\ 1 \end{matrix}\right)

Can it be reduced to a 3 imes 3 matrix exponentiation?

2 Likes

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

@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

I saw that recurrence relation on Quora :-

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

1 Like

delete. :pppp

1 Like

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} imes \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.

Please do some research before asking questions

1 Like

Thanks bro

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

1 Like

Question link, please.

Or Can anyone else confirm this?

In case if this is found true -

Then @karangreat234 this is your second offence of asking doubt related to ongoing hackererath problems.

First hackerearth question

I finally got the answer by myself .LOL.

nope, we canâ€™t, because if we reduce it to a 3X3 matrix, then the recurrence relation wonâ€™t hold anymore

but, its awesome !