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: > > 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. > >
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.
