Assignment 5

CS 680-503 Computer Algebra I
Instructor: Jeremy Johnson 
Due Wed. Feb. 9 in class



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

  1. First choice of problems:
    1. 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).
    2. 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).
  2. Second choice of problems:
    1. 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.
    2. 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.
    3. 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.