we can use the following formula to calculate the nth fibonacci no. in O(log n) time : fib(n)=round((pow(phi,n))/sqrt(5) + 1/2) where phi=(1+sqrt(5))/2;
And by taking care of the special cases and by using the fact that the problem is just to find the (N+3)th fibonacci number for given N, we can proceed.... On Mon, May 23, 2011 at 8:17 AM, Aakash Johari <[email protected]>wrote: > @akshata, sravanreddy: yes, for more info regarding matrix expo. you can go > through http://zobayer.blogspot.com/2010/11/matrix-exponentiation.html > > > On Mon, May 23, 2011 at 7:28 AM, Akshata Sharma <[email protected] > > wrote: > >> @sravanreddy001 >> by matrix exponential method, we can calculate the nth fibonacci number in >> logarithmic time. >> >> >> On Mon, May 23, 2011 at 7:39 PM, anshu mishra >> <[email protected]>wrote: >> >>> @sravanreddy001 >>> suppose u have to calulate A^n u can calculate in O(d^3*log(n)); >>> d is dimesion of matrixl >>> while (n) >>> { >>> if (n&1) mul(ans, A, d); >>> mul(A, A, d); >>> n >>=1; >>> } >>> >>> >>> -- >>> Anshuman Mishra >>> IIIT Allahabad >>> ----------------- >>> >>> [email protected] >>> [email protected] >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]. >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > > > -- > -Aakash Johari > (IIIT Allahabad) > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
