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

×

# Is there any formula to calculate nth fibonacci number ?

 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 ! :-) asked 18 Jan, 09:18 -863●9 accept rate: 0% 1 Please do some research before asking questions :/ https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ (18 Jan, 11:04) 1 Use Matrix Exponentiation to calculate it in log(N) time,it will be helpful. :) (18 Jan, 17:10) I finally got the answer by myself .LOL. (19 Jan, 11:02)

 1 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 answered 18 Jan, 10:05 78●6 accept rate: 7% Thanks bro :) (18 Jan, 12:53)
 1 delete. :pppp answered 19 Jan, 21:07 2.7k●1●6●18 accept rate: 10%
 2 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 \times 3$ matrix exponentiation? answered 19 Jan, 01:40 605●1●7 accept rate: 26% nope, we can't, because if we reduce it to a 3X3 matrix, then the recurrence relation won't hold anymore :-) (24 Jan, 19:06) but, its awesome ! :-) (28 Feb, 19:14)
 2 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.. answered 19 Jan, 08:43 4★spam_123 61●2 accept rate: 0% 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 (19 Jan, 09:36) (19 Jan, 11:17) spam_1234★
 1 @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 :- https://www.quora.com/How-do-I-simplify-a-recursion-equation-The-equation-is-f-n-2-n-3-f-n-3-f-n-1-We-are-given-the-values-f-0-f-1-f-2-Is-it-possible-to-get-an-expression-in-terms-of-n-for-f-n So to satisfy my curiosity, I asked it here. Sorry for such a big mistake. answered 19 Jan, 11:01 -863●9 accept rate: 0%
 0 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. answered 28 Feb, 22:07 2★brij_raj 76●7 accept rate: 10%
 toggle preview community wiki:
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:

×157
×38
×11

question asked: 18 Jan, 09:18

question was seen: 577 times

last updated: 28 Feb, 22:07