小声说一下
def fib(n):
	a=0
	b=1
	for i in xrange(n-1):
		t=a+b
		a=b
		b=t
	return b
在我的机器上只要27微秒...
由于jit会做缓存之类的优化,这样的比较才有意义...
测试算法的复杂度O(fib(n))
展开double recursion的复杂度O(n)
对于36来说
fib(36):n=14930352:36
例子就是比较各个语言函数调用的开销而已(jit的展开可以减少开销,函数调用开销小的语言就是比较print的效率)
在能识别double recursion之前jit再好也没人脑有用...
另外...对于超大的fibonacci来说...
令A=matrix([[1,1],[0,1]])
有[fib(n+1),fib(n)]=[fib(n),fib(n-1)]*A
所以对于n>1来说,有[fib(n),fib(n-1)]=[1,0]*(A^(n-1))
而A^(n-1)可以用指数法做,复杂度只有O( (log n)^3)


在 07-11-30，东子/hydon<hydonlee在gmail.com> 写道：
> IronPython版::
>
> def fib(n):
>    if n == 0 or n == 1:
>       return n
>    else:
>       return fib(n-1) + fib(n-2)
>
> from System import *
>
> dt1 = DateTime.Now
> for i in range(36):
>     print "n=%d => %d" % (i, fib(i))
> print DateTime.Now - dt1
>
> 时间: 00:00:19.8906250
>
> XP sp2, .net 2.0, IronPython 2.0A6,
> DELL 1501n:: AMD Sempron 3500+, 1G memory
>
> 在07-11-30， 沈崴 <wileishn在gmail.com> 写道：
> > YARV vs Psyco ...
> >
> > 在 07-11-30，swordsp<sparas2006在gmail.com> 写道：
> > > On 11/30/07, doudou doudou <array.doudou在gmail.com> wrote:
> > > > 晕，相同的算法，C的时间为0.576s。
> > >
> > > 你确定真的是"相同的算法"么？
> > > 我是说，加上了（python内建的）高精度处理么？
> > >
> > > 很多评测里python这样的脚本语言和c比起来都是吃亏在这种地方，其实是不公平的。
> > > _______________________________________________
> > > python-chinese
> > > Post: send python-chinese在lists.python.cn
> > > Subscribe: send subscribe to
> python-chinese-request在lists.python.cn
> > > Unsubscribe: send unsubscribe to
> python-chinese-request在lists.python.cn
> > > Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
> > _______________________________________________
> > python-chinese
> > Post: send python-chinese在lists.python.cn
> > Subscribe: send subscribe to
> python-chinese-request在lists.python.cn
> > Unsubscribe: send unsubscribe to
> python-chinese-request在lists.python.cn
> > Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
>
>
>
> --
> 东子!
> 努力做好每一件事!!!
> _______________________________________________
> python-chinese
> Post: send python-chinese在lists.python.cn
> Subscribe: send subscribe to
> python-chinese-request在lists.python.cn
> Unsubscribe: send unsubscribe to
> python-chinese-request在lists.python.cn
> Detail Info:
> http://python.cn/mailman/listinfo/python-chinese
>

呃...用numpy试了一下
>>> from numpy import matrix
>>> A=matrix([[1,1],[1,0]])
>>> beginvector=matrix([1,0])
>>> def fib(n):
	return (beginvector*(A**n))[0,1]
n=36的时候17微秒的样子...不过坏处就是n大了会溢出

继续来玩...
sage: FIBM=MatrixSpace(ZZ,2)
sage: A=FIBM([[1,1],[1,0]])
sage: FIBV=MatrixSpace(ZZ,1,2)
sage: beginVector=FIBV([1,0])
sage: def fib(n):
....:     return (beginVector*(A**n))[0][1]
....:
sage: import time
sage: def testfib(n):
....:     btime=time.time()
....:     r=fib(n)
....:     print time.time()-btime
....:     print r
....:
sage: testfib(36)
0.0206701755524
14930352
sage: testfib(300)
0.000365018844604
222232244629420445529739893461909967206666939096499764990979600
sage: testfib(36)
0.000303030014038
14930352
sage: testfib(1000)
0.000423908233643
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

在 07-12-1，yuting cui<yutingcui在gmail.com> 写道：
> 呃...用numpy试了一下
> >>> from numpy import matrix
> >>> A=matrix([[1,1],[1,0]])
> >>> beginvector=matrix([1,0])
> >>> def fib(n):
>         return (beginvector*(A**n))[0,1]
> n=36的时候17微秒的样子...不过坏处就是n大了会溢出
>