# Assignment 5

###
CS 680-503 Computer Algebra I

Instructor: Jeremy Johnson

Due Wed. Feb. 9 in class

### Overview

This assignment involves further exploration with the Euclidean
algorithm, SACLIB, and computing time analysis.
In this assignment I have provided to possible sets of problems.
You only need to hand in one of the possible sets of problems.
You may do both for extra credit.

### Problems to Hand in

- First choice of problems:
- Let F_n denote the nth Fibonacci number. Earlier in class we
remarked that F_n is approximately c*phi^n, where phi = 1/2 + sqrt(5)/2.
From this we can conclude that L(F_n) is codominant with n, where L
is the length function. Use this to prove that the time to compute
gcd(c*F_{n-k},c*F_{n-k-1}) using the Euclidean algorithm is codominant
with n*(n-k), where k = L(c). Next show that if c*F_{n-k} is replaced
with c*F_{n-k} + q*c*F_{n-k-1}, where L(q) = m-n+1, is codominant
with n*(m-k+1).
- Write a C program using SACLIB that generates pairs of inputs
(A,B) with L(A) = m, L(B) = n, and L(gcd(A,B)) = k. You can accomplish
that by generating random Ab, Bb, and C with L(Ab) = m-k, L(Bb) = m-k,
L(C) = k, and gcd(Ab,Bb) = 1, and letting A = Ab*C and B = Bb*C.
Your program should generate paris (A,B) for different values of m, n, and
k and measure the time to compute gcd(A,B) using the SACLIB function
IGCD. After obtaining sufficient timings, compare your empirical results
to the theoretical computing time bound n*(m-k+1).

- Second choice of problems:
- Obtain a tight bound on the maximum computing time of the SACLIB function
IEXP(A,n) as a function of d = L(A) and n.
- Suppose IEXP were to instead compute A^n using the following algorithm

if (n == 0) return 1

else {

B = 1;

for (i=1;i<=n;i++)

B = B * A;

}

return B;

Obtain a tight upper bound on this version of IEXP as a function of d = L(A)
and n.
- Implement the version of IEXP in the previous question using SACLIB
and compare its empircal computing time to that of the SACLIB function
IEXP. You should obtain runtimes for inputs with different values of
d = L(A) and n. To do so, you should generate a random integer A with
d BETA-digits (i.e. with L_BETA(A) = d). In addition to comparing
the two programs, you should compare the empirical runtimes to the
theoretical bounds obtained in the previous two questions.