#OK to post homework
#Jason Saied, April 19, 2019, Assignment 23

#given a nonnegative integer n, gives the binary expansion of n 
#in the form of a table T, where i is in the index set of T if and only if
#2^i has a nonzero coefficient in the binary expansion of n 
Binary:=proc(n) local k, m, L:

	m:=n:
	L:=[]:

	while m > 0 do
		
		k:=trunc(evalf(log[2](m))):
		m:=m-2^k:
		L:=[k,op(L)]:
		
	od:

	return L:

end:

#computes A^p modulo K, efficiently
Pow:=proc(A,p, K) local L, P, q, i, M:

	if A = 0 then 
		return 0:
	elif p=0 then
		return 1:
	fi:
	
	#L is the list of powers of A that we'll need
	L:=Binary(p):
	
	M:=A mod K:
	
	#run from 0 to the highest q such that 2^q appears in p's binary expansion 
	if member(0,L) then
		P:=[M]:
	else 
		P:=[]:
	fi:
	
	for q from 1 to L[nops(L)] do
	
		M:=M^2 mod K:
		#if q is a power we care about, store m=A^(2^q)
		if member(q,L) then
		
			P:=[op(P),M]:
		
		fi:
	
	od:
	
	#I was getting errors using product on matrices, so let's do this instead
	#the variable M is now being used for the product 
	M:=P[1]:
	for i from 2 to nops(P) do
	
		M:=M.P[i]:
	
	od:
	
	return M mod K:

end:

#quickly computes the nth Fibonacci number modulo K
Fc:=proc(n,K):
	
	if n=0 or n=1 then 
		return n:
	fi:

	with(LinearAlgebra):
	
	(Pow(Matrix([[1,1],[1,0]]), n,K).Matrix([[1],[0]]))[1,1]:

end:

#using the same trick, computes the nth Tribonacci number modulo K
Tc:=proc(n,K):

	if n=0 or n=1 then
		return 0:
	elif n=2 then
		return 1:
	fi:
	
	with(LinearAlgebra):
	
	(Pow(Matrix([[1,1,1],[1,0,0],[0,1,0]]),n,K).Matrix([[1],[0],[0]]))[1,1]:

end:

#Tc(10^100, 2003)=1995


#####taken from class

#C23.txt, April 18, 2019, Computing derivatives and gradients of complicated functions
Help23:=proc(): print(`Box(n), IsGG(v) , Fsss(n) , Fss(n) , Fs(n), F(n,K) , EvalC(L,x,x0)`): 
print(`RP(x,d,K), RC(x,d,K,n) , EvalCD(L,x,x0) `):
end:

#Box(n): the set of 0-1 vectors of lenght n
Box:=proc(n) local S,s:
if n=0 then
  RETURN({[]}):
else 
 S:=Box(n-1):
 
RETURN({seq([op(s),0], s in S),seq([op(s),1], s in S)}):
fi:
end:

#IsGG(v): Does v contain 11
IsGG:=proc(v) local i:

for i from 1 to nops(v)-1 do
  if v[i]=1 and v[i+1]=1 then
    RETURN(false):
  fi:
od:
true:
end:
 
#Fsss(n):the n-th Fibonacci number using the extremely stupid way
#One of the Combinatorial definition of fibonacci number, the number
#of 0-1 vectors of length n avoiding 11
Fsss:=proc(n) local S,G,co,s:
S:=Box(n):
co:=0:

for s in S do
 if IsGG(s) then
  co:=co+1:
 fi:
od:
co:
end:


#Fss(n): the n-th Fibonacci number using the very stupid way
Fss:=proc(n):
if n=0 or n=1 then
 n:
else
 Fss(n-1)+Fss(n-2):
fi:
end:

#Fs(n): the n-th Fibonacci number using the usual way mod K
Fs:=proc(n,K)
option remember:
if n=0 or n=1 then
 n:
else
 Fs(n-1,K)+Fs(n-2,K) mod K:
fi:
end:

#F(n,K): the n-th Fibonacci number the clever way mod K
F:=proc(n,K) local a,b,c,i:

a:=0:
b:=1:

for i from 1 to n do
c:=a+b mod K:
a:=b:
b:=c:
od:
a:
end:

#RP(x,d,K): a random poly in x of degree k with coefficients from 1 to K do
RP:=proc(x,d,K) local ra,i:
ra:=rand(1..K):

add(ra()*x^i,i=0..d):

end:
#RC(x,d,K,n): a random chain of length n of poly in x of degree k with coefficients from 1 to K do
RC:=proc(x,d,K,n) local i:
[seq(RP(x,d,K),i=1..n)]:
end:

 #[x0->x1->x2-> ... ->xn] 

  #EvalC(L,x,x0): inputs a listL of expressions in the variable x and a number x0
   #outputs L[n](L[n-1](.... L[1](x0))))))))) mod K:
  #x0->L[1](x0)->L[2](L[1](x0))-....
 EvalC:=proc(L,x,x0) local a,i:
  a:=x0:
   for i from 1 to nops(L) do
     a:=subs(x=a,L[i]):
   od:
a:
end:


 #EvalCD(L,x,x0): inputs a listL of expressions in the variable x and a number x0
   #outputs L[n](L[n-1](.... L[1](x0))))))))) followed by the derivative of the composition
   #at x0:
  #x0->L[1](x0)->L[2](L[1](x0))-....
  #f(g(x))'= f'(g(x))*g'(x) . (F[i](Previous(x)))'(x0)= F[i]'(Previoius(x)|x=x0)* (Previous'(x)|x=x0)
 EvalCD:=proc(L,x,x0) local a,b,i:
  a:=x0:
   b:=1:
   for i from 1 to nops(L) do
      b:=b*subs(x=a,diff(L[i],x)) :
     a:=subs(x=a,L[i]):
     
   od:
a,b:
end: