# 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

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 "", line 1, in File "_sage_input_36.py", line 10, in 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 File "/tmp/tmpgFfIll/___code___.py", line 3, in exec compile(u'len(myfib(_sage_const_10000000 ).digits()) File "", line 1, in 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