This doesn't work, as you have to take care of precision (try computing fib(100000)). I suspect that it's also slower when you do that, though Fredrik would have to comment.
Also, note that we already have a GoldenRation object. Aaron Meurer On Tue, Aug 2, 2011 at 3:47 PM, Matthew Rocklin <mrock...@gmail.com> wrote: > What's wrong with the old golden ratio trick to compute the Fibonacci > sequence?. > phi = (1+sqrt(S(5)))/2 > def fib(n): > return floor(phi**n / sqrt(5) + S.Half) > map(fib, range(10)) > [0, 1, 1, 2, 3, 5, 8, 13, 21, 34] > > On Tue, Aug 2, 2011 at 3:22 PM, Hector <hector1...@gmail.com> wrote: >> >> >> On Wed, Aug 3, 2011 at 1:42 AM, Vladimir Perić <vlada.pe...@gmail.com> >> wrote: >>> >>> On Tue, Aug 2, 2011 at 10:08 PM, Fredrik Johansson >>> <fredrik.johans...@gmail.com> wrote: >>> > On Tue, Aug 2, 2011 at 9:47 PM, Hector <hector1...@gmail.com> wrote: >>> >> Hello folk, >>> >> >>> >> I was browsing through the code and found that fibonacci numbers are >>> >> calculated by recursion method. So the time complexity is of O(n) and >>> >> I >>> >> don't expect space complexity be any optimal. It gave me the following >>> >> results. >>> > >>> >> There exists a algorithm which can calculate n^th fibonacci number in >>> >> O(ln(n)) times. It only requires to calculate few fibonacci numbers ( >>> >> approximately ln(n)/ln(2) ) to calculate F_n. I implemented it and it >>> >> shows >>> >> the following results. >>> > >>> > Just to nitpick: the recursive method has time complexity O(n^2) (the >>> > SymPy version is terrible for large n due to also using O(n^2) memory) >>> > and the fast algorithm has time complexity about O(n^1.6) (with Python >>> > arithmetic). >>> > >>> > I'm also not sure why your code is so complex (and it's not entirely >>> > obvious that it's correct). Something like this is much nicer: >>> > >> >> I would try to make it more simpler to read and understand. >> >> >>> >>> > def fib(n): >>> > a, b, p, q = 1, 0, 0, 1 >>> > while n: >>> > if n % 2: >>> > a, b = (a+b)*q + a*p, b*p + a*q >>> > n -= 1 >>> > else: >>> > t = q*q >>> > p, q = p*p + t, t + 2*p*q >>> > n //= 2 >>> > return b >>> > >>> > Fredrik >>> > >>> > -- >>> > You received this message because you are subscribed to the Google >>> > Groups "sympy" group. >>> > To post to this group, send email to sympy@googlegroups.com. >>> > To unsubscribe from this group, send email to >>> > sympy+unsubscr...@googlegroups.com. >>> > For more options, visit this group at >>> > http://groups.google.com/group/sympy?hl=en. >>> > >>> > >>> >> >> I am unable to find the algorithm written somewhere on the web and hence >> can't refer it. But I am sure about the formula I had used. The formula is >> there on the wikipedia page also[0] at the end of the section matrix form. >> >> [0] http://en.wikipedia.org/wiki/Fibonacci_number >>> >>> Yeah, like Mateusz noted, you should probably include some more info >>> in the commit message. You should also reference the algorithm used, >>> preferably both in the commit message and in the code (in a doctest, >>> for example). >>> >>> -- >>> Vladimir Perić >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "sympy" group. >>> To post to this group, send email to sympy@googlegroups.com. >>> To unsubscribe from this group, send email to >>> sympy+unsubscr...@googlegroups.com. >>> For more options, visit this group at >>> http://groups.google.com/group/sympy?hl=en. >>> >> >> >> >> -- >> -Regards >> Hector >> Whenever you think you can or you can't, in either way you are right. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "sympy" group. >> To post to this group, send email to sympy@googlegroups.com. >> To unsubscribe from this group, send email to >> sympy+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/sympy?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "sympy" group. > To post to this group, send email to sympy@googlegroups.com. > To unsubscribe from this group, send email to > sympy+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/sympy?hl=en. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To post to this group, send email to sympy@googlegroups.com. To unsubscribe from this group, send email to sympy+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
