2022/09/07 Math 3600 002 Fibonacci

374 days ago by brhatch

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 previous numbers b=a # sets the first number to the previous a=f # sets the second number to the current fib i+=1 return(f) 
       
my_fib(10) 
        
89
89
t=cputime() print(my_fib(10)) print(cputime()-t) 
        
89
6.7e-05
89
6.7e-05
t=cputime() print(my_fib(100)) print(cputime()-t) 
        
573147844013817084101
0.000102
573147844013817084101
0.000102
t=cputime() print(my_fib(10^3)) print(cputime()-t) 
        
703303677114228158218352548771835497701812698363587327426049050871545371\
181969335797422494945626117334877504492417659910881863632654502236471060\
12053374121273867339111198139373125598767690091902245245323403501
0.000597
70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
0.000597
t=cputime() print(my_fib(10^4) %10^20) print(cputime()-t) 
        
60676846711185597501
0.008592
60676846711185597501
0.008592
t=cputime() print(my_fib(10^5)%10^20) print(cputime()-t) 
        
38285979669707537501
0.107718
38285979669707537501
0.107718
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_26.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dD1jcHV0aW1lKCkKcHJpbnQobXlfZmliKDEwXjcpJTEwXjIwKQpwcmludChjcHV0aW1lKCktdCk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmp4i_xS6/___code___.py", line 4, in <module>
    print(my_fib(_sage_const_10 **_sage_const_7 )%_sage_const_10 **_sage_const_20 )
  File "/tmp/tmp7Rt2gz/___code___.py", line 12, in my_fib
    f=a+b     # The sum of the two previous 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 n=10^7 in realistic time. Lets improve things by finding a smarter way 
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 previous numbers b=a # sets the first number to the previous a=f # sets the second number to the current fib i+=1 return(f) 
       
t=cputime() print(my_fib(10^6)) print(cputime()-t) 
        
50046042277359244926937501
0.675313
50046042277359244926937501
0.675313
t=cputime() print(my_fib(10^7)) print(cputime()-t) 
        
500208210416153997120937501
7.09461
500208210416153997120937501
7.09461
t=cputime() print(my_fib(10^8)) print(cputime()-t) 
        
5000061634304001519060937501
70.914919
5000061634304001519060937501
70.914919
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.000139999999988
89
0.000139999999988
t=cputime() print(my_fibr(10^2)) print(cputime()-t) 
        
WARNING: Output truncated!  
full_output.txt



Traceback (click to the left of this block for traceback)
...
__SAGE__
WARNING: Output truncated!  
full_output.txt



^CTraceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_40.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("dD1jcHV0aW1lKCkKcHJpbnQobXlfZmlicigxMF4yKSkKcHJpbnQoY3B1dGltZSgpLXQp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmps8R0lR/___code___.py", line 4, in <module>
    print(my_fibr(_sage_const_10 **_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr

...

    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  File "/tmp/tmpR9l2En/___code___.py", line 8, in my_fibr
    return(my_fibr(n-_sage_const_1 )+my_fibr(n-_sage_const_2 ))
  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__
t=cputime() print(my_fib(10^3)) print(cputime()-t) 
        
45091902245245323403501
0.000788999999997
45091902245245323403501
0.000788999999997
t=cputime() print(my_fib(10^4)) print(cputime()-t) 
        
500160676846711185597501
0.00726800000001
500160676846711185597501
0.00726800000001
t=cputime() print(my_fib(10^5)) print(cputime()-t) 
        
5003838285979669707537501
0.071075
5003838285979669707537501
0.071075
t=cputime() print(my_fib(10^6)) print(cputime()-t) 
        
50046042277359244926937501
0.708356
50046042277359244926937501
0.708356
t=cputime() print(my_fib(10^7)) print(cputime()-t) 
        
500208210416153997120937501
7.077623
500208210416153997120937501
7.077623