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.
In [1]: %timeit F_n = fibonacci(100000)
100000 loops, best of 3: 10.2 us per loop
In [2]: %timeit F_n = fibonacci(1000000)
ERROR: Internal Python error in the inspect module.
Below is the traceback from this internal error.
Traceback (most recent call last):
File "/usr/lib/pymodules/python2.6/IPython/ultraTB.py", line 608, in
text
records = _fixed_getinnerframes(etb, context,self.tb_offset)
File "/usr/lib/pymodules/python2.6/IPython/ultraTB.py", line 224, in
_fixed_getinnerframes
records = fix_frame_records_filenames(inspect.getinnerframes(etb,
context))
File "/usr/lib/python2.6/inspect.py", line 942, in getinnerframes
framelist.append((tb.tb_frame,) + getframeinfo(tb, context))
File "/usr/lib/python2.6/inspect.py", line 902, in getframeinfo
filename = getsourcefile(frame) or getfile(frame)
File "/usr/lib/python2.6/inspect.py", line 451, in getsourcefile
if hasattr(getmodule(object, filename), '__loader__'):
File "/usr/lib/python2.6/inspect.py", line 494, in getmodule
os.path.realpath(f)] = module.__name__
MemoryError
Unfortunately, your original traceback can not be constructed.
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.
In [1]: %timeit F_n = fibonacci(100000)
100000 loops, best of 3: 3.17 us per loop
In [2]: %timeit F_n = fibonacci(1000000)
1 loops, best of 3: 5.96 us per loop
In [3]: %timeit F_n = fibonacci(10000000)
1 loops, best of 3: 5.01 us per loop
I made the pull request regarding the same[0] after 'rebase'-ing it to
master. Hope I don't mess up with rebase-ing thing this time.
--
-Regards
Hector
Whenever you think you can or you can't, in either way you are right.
[0] https://github.com/sympy/sympy/pull/526
--
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.
