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.
