2022.01.24 MATH 3600 Fibonacci

124 days ago by calkin

fibonacci(0) 
        
0
0
fibonacci(1) 
        
1
1

How can we compute the first 10 fibonacci numbers (badly)?
0+1 
        
1
1
1+1 
        
2
2
2+1 
        
3
3
3+2 
        
5
5
5+3 
        
8
8
8+5 
        
13
13
13+8 
        
21
21
 
       
21+13 
        
34
34
34+21 
        
55
55

Clearly the wrong way to do things!
previous_value=0 current_value=1 current_index=2 while current_index <= 100: next_value=current_value+previous_value # Compute the next Fibonacci number previous_value = current_value # switch the current pair out for the subsequent pair current_value = next_value current_index += 1 
       
print current_value 
        
354224848179261915075
354224848179261915075
fibonacci(100) 
        
354224848179261915075
354224848179261915075

Next modification: Start with n=desired index to compute
n=100 previous_value=0 current_value=1 current_index=2 while current_index <= n: next_value=current_value+previous_value # Compute the next Fibonacci number previous_value = current_value # switch the current pair out for the subsequent pair current_value = next_value current_index += 1 print current_value 
        
354224848179261915075
354224848179261915075

Now let's define a function myfib(n) which will return the nth fibonacci number
def myfib(n): previous_value=0 current_value=1 current_index=2 while current_index <= n: next_value=current_value+previous_value # Compute the next Fibonacci number previous_value = current_value # switch the current pair out for the subsequent pair current_value = next_value current_index += 1 return(current_value) 
       
len(myfib(10000000).digits()) 
        
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_36.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bGVuKG15ZmliKDEwMDAwMDAwKS5kaWdpdHMoKSk="),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpgFfIll/___code___.py", line 3, in <module>
    exec compile(u'len(myfib(_sage_const_10000000 ).digits())
  File "", line 1, in <module>
    
  File "/tmp/tmp3AecZU/___code___.py", line 8, in myfib
    next_value=current_value+previous_value  # Compute the next Fibonacci number
  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__
len(fibonacci(10000000).digits()) 
        
2089877
2089877
len(fibonacci(10000000).digits(2)) 
        
6942418
6942418

F($10^7$) has around 2 million digits: too many to handle!  Let's instead just ask for the final ten digits.

So, do our computations modulo $10^{10}$.
def myfibbetter(n): previous_value=mod(0,10^10) current_value=mod(1,10^10) current_index=2 while current_index <= n: next_value=current_value+previous_value # Compute the next Fibonacci number previous_value = current_value # switch the current pair out for the subsequent pair current_value = next_value current_index += 1 return(current_value) 
       
myfibbetter(100) 
        
9261915075
9261915075
myfibbetter(10^6) 
        
8242546875
8242546875
myfibbetter(10^7) 
        
6380546875
6380546875