2022.02.18 MATH 3600 Fibonacci revisited

134 days ago by calkin

fibonacci(0) 
        
0
0
fibonacci(1) 
        
1
1
fibonacci(10) 
        
55
55

Let's write some bad code and see if we can test how many recursive calls it makes.
fibcounter=0 def my_fib_bad(n): # compute F(n) by recursive calls global fibcounter if n<0 or (type(n)==Integer)==False: # Check for incorrect inputs return("bad input") fibcounter+=1 if n==0: return(0) elif n==1: return(1) else: return(my_fib_bad(n-1)+my_fib_bad(n-2)) 
       
fibcounter=0 my_fib_bad(35) print(fibcounter) 
       
fibonacci(3500) 
        
128013529779468136153585136825101961538900481122065445964837651183086898\
754026550517136497483483470641608626276464055059332628575928521597999901\
718592957423352363167465917636140408184822379391543598931815814725878528\
845711814356562816020703656120345663431005792446926782064141406206872674\
044496382612109555705276756054608939403080010257497520565825039141232590\
185236536300243432404427078483449695275223922784635210975743019657462141\
365577883788628334421325013343898945369582265133225052581547429120787483\
968895443714869214153983484196368957200111230649716136282989616442150717\
747827588840460128198812637224475960962985001698982034192388374058622072\
865322851268191822192497641904232912275607663029887240803055414422300714\
028137340125
128013529779468136153585136825101961538900481122065445964837651183086898754026550517136497483483470641608626276464055059332628575928521597999901718592957423352363167465917636140408184822379391543598931815814725878528845711814356562816020703656120345663431005792446926782064141406206872674044496382612109555705276756054608939403080010257497520565825039141232590185236536300243432404427078483449695275223922784635210975743019657462141365577883788628334421325013343898945369582265133225052581547429120787483968895443714869214153983484196368957200111230649716136282989616442150717747827588840460128198812637224475960962985001698982034192388374058622072865322851268191822192497641904232912275607663029887240803055414422300714028137340125

Let's write a bottom up function to compute F(n)
def my_fib_better(n): # bottom up program to compute F(n) if n<0 or (type(n)==Integer)==False: # Check for incorrect inputs return("bad input") if n==0: return(0) elif n==1: return(1) else: i=0 a=1 b=0 while i<n-1: c=a+b # add the previous two fibonacci numbers b=a # update the smaller number a=c # update the larger number i+=1 # increment the step counter return(c) 
       
len(my_fib_better(4000000).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_45.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("bGVuKG15X2ZpYl9iZXR0ZXIoNDAwMDAwMCkuZGlnaXRzKCkp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmpGn0lxW/___code___.py", line 3, in <module>
    exec compile(u'len(my_fib_better(_sage_const_4000000 ).digits())
  File "", line 1, in <module>
    
  File "/tmp/tmp6d3lKp/___code___.py", line 15, in my_fib_better
    c=a+b    # add the previous two fibonacci 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__

Clearly the second program works better than the first.  But keeping all the digits is messing things up.  Let's just keep 20 digits.
def my_fib_faster(n): # bottom up program to compute F(n) if n<0 or (type(n)==Integer)==False: # Check for incorrect inputs return("bad input") if n==0: return(0) elif n==1: return(1) else: i=0 a=1 b=0 while i<n-1: c=a+b % 10^20 # add the previous two fibonacci numbers b=a # update the smaller number a=c # update the larger number i+=1 # increment the step counter return(c) 
       
my_fib_faster(400000) 
        
20015045536383715033346875
20015045536383715033346875
my_fib_faster(4000000) 
        
200098789059742454288546875
200098789059742454288546875

This works better for computing the final 20 digits of F(n)!

Your individual $n$ is going to be $n=7^k$ where $k$ is your 8 digit CUID.

Your assignment is to compute the final 20 digits of $F_n$.

117= 64+32+16+4+1
a=mod(1,10^20) A=matrix(2,2,[a,a,a,0]) 
       
A2=A*A A4=A2*A2 A8=A4*A4 A16=A8*A8 A32=A16*A16 A64=A32*A32 show(A64*A32*A16*A4*A) show(A^117) 
       
type(a) 
        
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
<type 'sage.rings.finite_rings.integer_mod.IntegerMod_gmp'>
type(1) 
        
<type 'sage.rings.integer.Integer'>
<type 'sage.rings.integer.Integer'>
B=matrix(2,2,[1,1,1,0]) 
       
show(B^217) 
       
show(A^217) 
       
show(A) show(B) 
       
M=matrix(2,2,[a,0,0,a]) B=A M=B*M # need A^1 B=B^2 # compute A^2 B=B^2 # compute A^4 M=B*M # need A^4 in the product B=B^2 # compute A^8 B=B^2 # compute A^16 M=B*M # need A^16 in the product B=B^2 # compute A^32 M=B*M # need A^32 in the product B=B^2 # compute A^64 M=M*B # need A^64 in the product show(M) show(A^117) 
       
n=117 n.digits(2) 
        
[1, 0, 1, 0, 1, 1, 1]
[1, 0, 1, 0, 1, 1, 1]
len((7^(10^8)).digits(2)) 
        
280735493
280735493

When raising numbers to a high power, things get very big very quickly!

When raising matrices to a high power, the same thing happens.

So we really do need to control the size of the results e.g. by taking things (mod n).
show(B^1217) 
       

Can  we explore other ways of doing things?  Let's think about arithmetic modulo n.
n=46 a=mod(17,46) # a=17 
       
powers_list=[] for i in srange(100): powers_list.append(a^i) 
       
show(powers_list) 
       

It appears that the sequence of powers of 17 (mod 46) repeats.

Why?
n=46 a=mod(23,46) # powers_list=[] for i in srange(100): powers_list.append(a^i) show(powers_list) 
       
n=14 for a in srange(1,n): a=mod(a,n) powers_list=[] for k in srange(2*n): powers_list.append(a^k) show(powers_list[1:]) 
       
n=13 for a in srange(1,n): a=mod(a,n) powers_list=[] for k in srange(2*n): powers_list.append(a^k) show(powers_list[1:])