2023.03.17 Math 3600 Revisiting Fibonacci

196 days ago by calkin

fibonacci(4) 
        
3
3

Why is recursion dangerous?  Let's compute fibonacci numbers recursively.
def my_fib_r(n): # recursive computation of fib(n) if n.is_integer()==False: return("n needs to be an integer") if n<0: return("n needs to be non-negative") if n==0: return(0) if n==1: return(1) return(my_fib_r(n-1)+my_fib_r(n-2)) 
       
my_fib_r(0) 
        
0
0
my_fib_r(1) 
        
1
1
my_fib_r(10) 
        
55
55
my_fib_r(-1) 
        
'n needs to be non-negative'
'n needs to be non-negative'
my_fib_r(.5) 
        
'n needs to be an integer'
'n needs to be an integer'
t=cputime() print(my_fib_r(30)) print(cputime()-t) 
        
832040
1.834607
832040
1.834607
cputime( 
       
t=cputime() print(my_fib_r(10)) print(cputime()-t) 
        
55
0.000287999999999
55
0.000287999999999
t=cputime() print(my_fib_r(20)) print(cputime()-t) 
        
6765
0.021829
6765
0.021829
t=cputime() print(my_fib_r(30)) print(cputime()-t) 
        
832040
1.81965
832040
1.81965
t=cputime() print(my_fib_r(40)) print(cputime()-t) 
        
Traceback (click to the left of this block for traceback)
...
__SAGE__
^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_19.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dD1jcHV0aW1lKCkKcHJpbnQobXlfZmliX3IoNDApKQpwcmludChjcHV0aW1lKCktdCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpzAMndY/___code___.py", line 4, in <module>
    print(my_fib_r(_sage_const_40 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 12, in my_fib_r
    return(my_fib_r(n-_sage_const_1 )+my_fib_r(n-_sage_const_2 ))
  File "/tmp/tmpvYMn2b/___code___.py", line 3, in my_fib_r
    def my_fib_r(n): # recursive computation of fib(n)
  File "sage/ext/interrupt/interrupt.pyx", line 203, in sage.ext.interrupt.interrupt.sage_python_check_interrupt (/usr/local/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:1891)
  File "sage/ext/interrupt/interrupt.pyx", line 88, in sage.ext.interrupt.interrupt.sig_raise_exception (/usr/local/sage-6.10/src/build/cythonized/sage/ext/interrupt/interrupt.c:925)
KeyboardInterrupt
__SAGE__
counter = 0 def my_fib_r(n): # recursive computation of fib(n) global counter counter +=1 if n.is_integer()==False: return("n needs to be an integer") if n<0: return("n needs to be non-negative") if n==0: return(0) if n==1: return(1) return(my_fib_r(n-1)+my_fib_r(n-2)) 
       
counter = 0 t=cputime() print(my_fib_r(10)) print(cputime()-t) print(counter) 
        
55
0.000261999999992
177
55
0.000261999999992
177
counter = 0 t=cputime() print(my_fib_r(20)) print(cputime()-t) print(counter) 
        
6765
0.026749
21891
6765
0.026749
21891
counter = 0 t=cputime() print(my_fib_r(30)) print(cputime()-t) print(counter) 
        
832040
2.227804
2692537
832040
2.227804
2692537
counter = 0 t=cputime() print(my_fib_r(35)) print(cputime()-t) print(counter) 
        
9227465
22.169936
29860703
9227465
22.169936
29860703
fibonacci(40) 
        
102334155
102334155

$F_n$ is the closest integer to $\frac{1}{\sqrt{5}} \left( \frac{1+\sqrt{5}}{2} \right)^n$.
phi= (1+sqrt(5.))/2 for n in srange(10): print(1/sqrt(5.)*phi^n) 
        
0.447213595499958
0.723606797749979
1.17082039324994
1.89442719099992
3.06524758424985
4.95967477524977
8.02492235949962
12.9845971347494
21.0095194942490
33.9941166289984
0.447213595499958
0.723606797749979
1.17082039324994
1.89442719099992
3.06524758424985
4.95967477524977
8.02492235949962
12.9845971347494
21.0095194942490
33.9941166289984

How big is $\frac{log(\phi)}{log(10)}$?
log(phi)/log(10.) 
        
0.208987640249979
0.208987640249979
t=cputime() print(log(fibonacci(10^6)).n()/log(10.)) print(cputime()-t) 
        
208987.290764977
0.009503
208987.290764977
0.009503
t=cputime() print(log(fibonacci(10^7)).n()/log(10.)) print(cputime()-t) 
        
2.08987605301478e6
0.263528
2.08987605301478e6
0.263528
t=cputime() print(log(fibonacci(10^8)).n()/log(10.)) print(cputime()-t) 
        
2.08987636755129e7
4.428707
2.08987636755129e7
4.428707
t=cputime() print(log(fibonacci(10^9)).n()/log(10.)) print(cputime()-t) 
        
2.08987639900494e8
45.316107
2.08987639900494e8
45.316107
for n in srange(624,644): print(mod(fibonacci(n),10^20)) 
        
12094869620734133568
73554788881298750625
85649658502032884193
59204447383331634818
44854105885364519011
4058553268696153829
48912659154060672840
52971212422756826669
1883871576817499509
54855083999574326178
56738955576391825687
11594039575966151865
68332995152357977552
79927034728324129417
48260029880682106969
28187064609006236386
76447094489688343355
4634159098694579741
81081253588382923096
85715412687077502837
12094869620734133568
73554788881298750625
85649658502032884193
59204447383331634818
44854105885364519011
4058553268696153829
48912659154060672840
52971212422756826669
1883871576817499509
54855083999574326178
56738955576391825687
11594039575966151865
68332995152357977552
79927034728324129417
48260029880682106969
28187064609006236386
76447094489688343355
4634159098694579741
81081253588382923096
85715412687077502837
for n in srange(624,644): l=fibonacci(n).digits(10) l.reverse() print(l[:20]) 
        
[1, 1, 4, 4, 9, 9, 2, 1, 6, 2, 2, 0, 7, 9, 7, 2, 1, 1, 5, 4]
[1, 8, 5, 2, 6, 3, 6, 2, 3, 5, 3, 0, 4, 7, 3, 1, 7, 3, 1, 0]
[2, 9, 9, 7, 6, 2, 8, 3, 9, 7, 5, 1, 2, 7, 0, 3, 8, 4, 6, 4]
[4, 8, 5, 0, 2, 6, 4, 6, 3, 2, 8, 1, 7, 4, 3, 5, 5, 7, 7, 5]
[7, 8, 4, 7, 8, 9, 3, 0, 3, 0, 3, 3, 0, 1, 3, 9, 4, 2, 3, 9]
[1, 2, 6, 9, 8, 1, 5, 7, 6, 6, 3, 1, 4, 7, 5, 7, 5, 0, 0, 1]
[2, 0, 5, 4, 6, 0, 5, 0, 6, 9, 3, 4, 7, 7, 7, 1, 4, 4, 2, 5]
[3, 3, 2, 4, 4, 2, 0, 8, 3, 5, 6, 6, 2, 5, 2, 8, 9, 4, 2, 6]
[5, 3, 7, 9, 0, 2, 5, 9, 0, 5, 0, 1, 0, 3, 0, 0, 3, 8, 5, 2]
[8, 7, 0, 3, 4, 4, 6, 7, 4, 0, 6, 7, 2, 8, 2, 9, 3, 2, 7, 9]
[1, 4, 0, 8, 2, 4, 7, 2, 6, 4, 5, 6, 8, 3, 1, 2, 9, 7, 1, 3]
[2, 2, 7, 8, 5, 9, 1, 9, 3, 8, 6, 3, 5, 5, 9, 5, 9, 0, 4, 1]
[3, 6, 8, 6, 8, 3, 9, 2, 0, 3, 2, 0, 3, 9, 0, 8, 8, 7, 5, 4]
[5, 9, 6, 5, 4, 3, 1, 1, 4, 1, 8, 3, 9, 5, 0, 4, 7, 7, 9, 5]
[9, 6, 5, 2, 2, 7, 0, 3, 4, 5, 0, 4, 3, 4, 1, 3, 6, 5, 4, 9]
[1, 5, 6, 1, 7, 7, 0, 1, 4, 8, 6, 8, 8, 2, 9, 1, 8, 4, 3, 4]
[2, 5, 2, 6, 9, 9, 7, 1, 8, 3, 1, 9, 2, 6, 3, 3, 2, 0, 8, 9]
[4, 0, 8, 8, 7, 6, 7, 3, 3, 1, 8, 8, 0, 9, 2, 5, 0, 5, 2, 4]
[6, 6, 1, 5, 7, 6, 4, 5, 1, 5, 0, 7, 3, 5, 5, 8, 2, 6, 1, 3]
[1, 0, 7, 0, 4, 5, 3, 1, 8, 4, 6, 9, 5, 4, 4, 8, 3, 3, 1, 3]
[1, 1, 4, 4, 9, 9, 2, 1, 6, 2, 2, 0, 7, 9, 7, 2, 1, 1, 5, 4]
[1, 8, 5, 2, 6, 3, 6, 2, 3, 5, 3, 0, 4, 7, 3, 1, 7, 3, 1, 0]
[2, 9, 9, 7, 6, 2, 8, 3, 9, 7, 5, 1, 2, 7, 0, 3, 8, 4, 6, 4]
[4, 8, 5, 0, 2, 6, 4, 6, 3, 2, 8, 1, 7, 4, 3, 5, 5, 7, 7, 5]
[7, 8, 4, 7, 8, 9, 3, 0, 3, 0, 3, 3, 0, 1, 3, 9, 4, 2, 3, 9]
[1, 2, 6, 9, 8, 1, 5, 7, 6, 6, 3, 1, 4, 7, 5, 7, 5, 0, 0, 1]
[2, 0, 5, 4, 6, 0, 5, 0, 6, 9, 3, 4, 7, 7, 7, 1, 4, 4, 2, 5]
[3, 3, 2, 4, 4, 2, 0, 8, 3, 5, 6, 6, 2, 5, 2, 8, 9, 4, 2, 6]
[5, 3, 7, 9, 0, 2, 5, 9, 0, 5, 0, 1, 0, 3, 0, 0, 3, 8, 5, 2]
[8, 7, 0, 3, 4, 4, 6, 7, 4, 0, 6, 7, 2, 8, 2, 9, 3, 2, 7, 9]
[1, 4, 0, 8, 2, 4, 7, 2, 6, 4, 5, 6, 8, 3, 1, 2, 9, 7, 1, 3]
[2, 2, 7, 8, 5, 9, 1, 9, 3, 8, 6, 3, 5, 5, 9, 5, 9, 0, 4, 1]
[3, 6, 8, 6, 8, 3, 9, 2, 0, 3, 2, 0, 3, 9, 0, 8, 8, 7, 5, 4]
[5, 9, 6, 5, 4, 3, 1, 1, 4, 1, 8, 3, 9, 5, 0, 4, 7, 7, 9, 5]
[9, 6, 5, 2, 2, 7, 0, 3, 4, 5, 0, 4, 3, 4, 1, 3, 6, 5, 4, 9]
[1, 5, 6, 1, 7, 7, 0, 1, 4, 8, 6, 8, 8, 2, 9, 1, 8, 4, 3, 4]
[2, 5, 2, 6, 9, 9, 7, 1, 8, 3, 1, 9, 2, 6, 3, 3, 2, 0, 8, 9]
[4, 0, 8, 8, 7, 6, 7, 3, 3, 1, 8, 8, 0, 9, 2, 5, 0, 5, 2, 4]
[6, 6, 1, 5, 7, 6, 4, 5, 1, 5, 0, 7, 3, 5, 5, 8, 2, 6, 1, 3]
[1, 0, 7, 0, 4, 5, 3, 1, 8, 4, 6, 9, 5, 4, 4, 8, 3, 3, 1, 3]
fibonacci(624) 
        
114499216220797211544971998999666779076389958966222193888436561948702044\
40338362332943924986323117322375295462212094869620734133568
11449921622079721154497199899966677907638995896622219388843656194870204440338362332943924986323117322375295462212094869620734133568

Computing $F_n$ via $A^n$ where 

\[ A= \begin{pmatrix}  1 & 1 \\ 1 & 0\end{pmatrix}  \]
A=matrix(2,2,[1,1,1,0]) print(A^10) 
        
[89 55]
[55 34]
[89 55]
[55 34]

This does indeed have entries $F_{11}, F_{10}, F_{10}, F_{9}$.
print(A^145) 
        
[1454489111232772683678306641953  898923707008479989274290850145]
[ 898923707008479989274290850145  555565404224292694404015791808]
[1454489111232772683678306641953  898923707008479989274290850145]
[ 898923707008479989274290850145  555565404224292694404015791808]

What if we only want to keep track of the final 20 digits?

Use sage's built in modular arithmetic.
a=mod(1,10^20) print(a) print(type(a)) 
        
1
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
1
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
type(1) 
        
<type 'sage.rings.integer.Integer'>
<type 'sage.rings.integer.Integer'>
a==1 
        
True
True
A=matrix(2,2,[a,a,a,0]) print(A^145) 
        
[32772683678306641953  8479989274290850145]
[ 8479989274290850145 24292694404015791808]
[32772683678306641953  8479989274290850145]
[ 8479989274290850145 24292694404015791808]