{{{id=1| def fiboRecur(n): """ suite de Fibonacci, récursif""" if(n<2): return 1 else: return fiboRecur(n-1)+fiboRecur(n-2) def fiboIter(n): """ suite de Fibonacci, non récursif""" a=1 b=1 for i in range(1,n): a,b=b,a+b return b def temps(n,ff): """ détermine le temps de calcul de ff(n) """ t = cputime() r = ff(n) return cputime()-t /// }}} {{{id=39| # test naïf de validité [fiboRecur(k) for k in range(15)] [fiboIter(k) for k in range(15)] /// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] }}} {{{id=40| fiboRecur(35) /// 14930352 }}} {{{id=2| # liste de temps de calculs avec la procédure récursive FiRec = [[n,temps(n,fiboRecur)] for n in range(23,36)] list_plot(FiRec) ///

}}} {{{id=3| # calcul et affichage des logarithmes N = [[p[0],ln(p[1])] for p in FiRec] list_plot(N) ///

}}} {{{id=6| # un ajustement linéaire sur les log semble pertinent ! var('a b') h(x) = a*x+b A=find_fit(N[1:],h,solution_dict=True) A[a],A[b] /// (0.47973203247579821, -14.551817546368314) }}} {{{id=7| list_plot(N)+plot(x*A[a]+A[b],(x,21,38),color='red') ///

}}} {{{id=8| # il y a du nombre d'or dans l'air exp(A[a]); numerical_approx((1+sqrt(5))/2,digits=6);fiboIter(5000)/fiboIter(4999).numerical_approx(digits=6) /// 1.6156414047536287 1.61803 1.61803 }}} {{{id=45| temps(5000,fiboIter) /// 0.0080010000000001469 }}} {{{id=31| L = [[n,temps(10000*n,fiboIter)] for n in range(20)] list_plot(L) ///

}}} {{{id=32| # un ajustement second degré var('a b c') k(x) = a*x^2+b*x+c B=find_fit(L,k,solution_dict=True) B[a],B[b],B[c] /// (0.00062295744826434962, 0.0012954528002819821, 0.0035637032445747785) }}} {{{id=46| list_plot(L)+plot(x^2*B[a]+B[b]*x+B[c],(x,0,20),color='red') ///

}}} {{{id=34| # récursivité avec conservation des résultats antérieurs # bien plus rapide que la récursivité naïve, bien sûr ! from functools import wraps def memo(func): cache={} @wraps(func) def wrap(*args): if args not in cache: cache[args]=func(*args) return cache[args] return wrap @memo def fibon(i): if i<2: return 1 return fibon(i-1)+fibon(i-2) /// }}} {{{id=48| M = [[n,temps(300*n,fibon)] for n in range(20)] list_plot(M,color="green") ///

}}} {{{id=49| # limitation : nombre d'étapes de récursivité autorisés fibon(10000) /// WARNING: Output truncated! full_output.txt Traceback (most recent call last): File "", line 1, in File "_sage_input_46.py", line 10, in exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("IyBsaW1pdGF0aW9uIDogbm9tYnJlIGQnw6l0YXBlcyBkZSByw6ljdXJzaXZpdMOpIGF1dG9yaXPDqXMKZmlib24oMTAwMDAp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))' + '\n', '', 'single') File "", line 1, in File "/tmp/tmptE_HHy/___code___.py", line 3, in exec compile(u'fibon(_sage_const_10000 )' + '\n', '', 'single') File "", line 1, in File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap ... return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) File "/tmp/tmpgIUtj7/___code___.py", line 21, in fibon return fibon(i-_sage_const_1 )+fibon(i-_sage_const_2 ) File "/tmp/tmpgIUtj7/___code___.py", line 12, in wrap cache[args]=func(*args) RuntimeError: maximum recursion depth exceeded }}} {{{id=50| # manipulation rapide de nombres gigantesques (affichage du nombre de chiffres) ln(fiboIter(500000)*1.)/ln(10.) /// 104493.679627627 }}} {{{id=36| # calcul des nombres de Fibonacci par les puissances d'une matrice def puissance(M,n): if n==0: return Matrix(2,2,[1,0,0,1]) if n%2==0: P = puissance(M,n/2) return P*P else: P = puissance(M,(n-1)/2) return P*P*M def fiboPuiss(n): M = Matrix(2,2,[1,1,1,0]) P = puissance(M,n) return P[0][0] /// }}} {{{id=38| [fiboPuiss(k) for k in range(15)] /// [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610] }}} {{{id=42| # efficacité comparée des algorithmes itératif et par puissances Ntest = 500000 temps(Ntest,fiboIter);temps(Ntest,fiboPuiss) /// 1.5800990000000041 0.028001999999993643 }}} {{{id=44| /// }}}