2022.09.09 Math 3600-002 Fibonacci

378 days ago by calkin

def My_Fib(n): a=1 # one back b=1 # two back i=2 while i<n+1: f=a+b # The sum of the two preceding Fib numbers b=a # Update the fib number two back a=f # Update the preceding fib number i+=1 return(f) 
       
My_Fib(1) 
        
Traceback (click to the left of this block for traceback)
...
UnboundLocalError: local variable 'f' referenced before assignment
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_10.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("TXlfRmliKDEp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpR8Rfrl/___code___.py", line 3, in <module>
    exec compile(u'My_Fib(_sage_const_1 )
  File "", line 1, in <module>
    
  File "/tmp/tmp5UalZZ/___code___.py", line 12, in My_Fib
    return(f)
UnboundLocalError: local variable 'f' referenced before assignment
def My_Fib(n): a=1 # one back b=1 # two back i=2 if n==0: return(1) if n==1: return(1) while i<n+1: f=a+b # The sum of the two preceding Fib numbers b=a # Update the fib number two back a=f # Update the preceding fib number i+=1 return(f) 
       
My_Fib(3) 
        
3
3
My_Fib(10) 
        
89
89

How far out can we compute in realistic time?
t=cputime() print(My_Fib(10)) print(cputime()-t) 
        
89
9.99999999998e-05
89
9.99999999998e-05
t=cputime() print(My_Fib(10^2)) print(cputime()-t) 
        
573147844013817084101
0.000168
573147844013817084101
0.000168
t=cputime() print(My_Fib(10^3)) print(cputime()-t) 
        
703303677114228158218352548771835497701812698363587327426049050871545371\
181969335797422494945626117334877504492417659910881863632654502236471060\
12053374121273867339111198139373125598767690091902245245323403501
0.000839
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
0.000839
t=cputime() print(My_Fib(10^4) %10^20) print(cputime()-t) 
        
60676846711185597501
0.009082
60676846711185597501
0.009082
t=cputime() print(My_Fib(10^5) %10^20) print(cputime()-t) 
        
38285979669707537501
0.096442
38285979669707537501
0.096442
t=cputime() print(My_Fib(10^6) %10^20) print(cputime()-t) 
        
42277359244926937501
7.198228
42277359244926937501
7.198228
t=cputime() print(My_Fib(10^7) %10^20) 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_23.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dD1jcHV0aW1lKCkgIApwcmludChNeV9GaWIoMTBeNykgJTEwXjIwKQpwcmludChjcHV0aW1lKCktdCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpvgro5r/___code___.py", line 4, in <module>
    print(My_Fib(_sage_const_10 **_sage_const_7 ) %_sage_const_10 **_sage_const_20 )
  File "/tmp/tmpaAAUVS/___code___.py", line 12, in My_Fib
    f=a+b  # The sum of the two preceding Fib numbers
  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__

We can't compute for $n=10^7$ in realistic time.
def My_Fib(n): a=1 # one back b=1 # two back i=2 if n==0: return(1) if n==1: return(1) while i<n+1: f=a+b %10^20 # The sum of the two preceding Fib numbers b=a # Update the fib number two back a=f # Update the preceding fib number i+=1 return(f) 
       
t=cputime() print(My_Fib(10^5) ) print(cputime()-t) 
        
5003838285979669707537501
0.070521
5003838285979669707537501
0.070521
t=cputime() print(My_Fib(10^6) ) print(cputime()-t) 
        
50046042277359244926937501
0.700159
50046042277359244926937501
0.700159
t=cputime() print(My_Fib(10^7) ) print(cputime()-t) 
        
500208210416153997120937501
7.013942
500208210416153997120937501
7.013942
t=cputime() print(My_Fib(10^8) ) print(cputime()-t) 
        
5000061634304001519060937501
70.100407
5000061634304001519060937501
70.100407
def My_Fibr(n): if n==0: return(1) if n==1: return(1) return(My_Fibr(n-1)+My_Fibr(n-2)) 
       
t=cputime() print(My_Fibr(10) ) print(cputime()-t) 
        
89
0.000142000000039
89
0.000142000000039
t=cputime() print(My_Fibr(20) ) print(cputime()-t) 
        
10946
0.00838799999997
10946
0.00838799999997
t=cputime() print(My_Fibr(30) ) print(cputime()-t) 
        
1346269
1.054996
1346269
1.054996
t=cputime() print(My_Fibr(32) ) print(cputime()-t) 
        
3524578
2.761668
3524578
2.761668
t=cputime() print(My_Fibr(35) ) print(cputime()-t) 
        
14930352
11.711825
14930352
11.711825
A=matrix(2,2,[1,1,1,0]) print(A^1000) 
        
[70330367711422815821835254877183549770181269836358732742604905087154537\
118196933579742249494562611733487750449241765991088186363265450223647106\
012053374121273867339111198139373125598767690091902245245323403501
434665576869374564356885276750406258025646605173717804024817290895365554\
179490518904038798400792551692959225930803226347752096896232398733224711\
61642996440906533187938298969649928516003704476137795166849228875]
[43466557686937456435688527675040625802564660517371780402481729089536555\
417949051890403879840079255169295922593080322634775209689623239873322471\
161642996440906533187938298969649928516003704476137795166849228875
268638100244853593861467272021429239676166093189869523401231759976179817\
002478816893383696544833565641918278561614433563129766736422103503246348\
50410377680367334151172899169723197082763985615764450078474174626]
[70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875]
[43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626]
a=mod(1,10^20) print(a*145134890512345615672344672274252524725247234) 
        
72274252524725247234
72274252524725247234
A=matrix(2,2,[a,a,a,0]) 
       
print(A^1000) 
        
[91902245245323403501 76137795166849228875]
[76137795166849228875 15764450078474174626]
[91902245245323403501 76137795166849228875]
[76137795166849228875 15764450078474174626]
n=7^99999999 
       
is_even(n) 
        
False
False
is_odd(n) 
        
True
True
print(n) 
        
0
0
n=0