Hi, On 2 August 2011 21:47, 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. > > 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. > Very nice. I left some technical remarks in the pull request. Can you also include the above discussion in the commit message? > > -- > -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. > Mateusz -- 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.
