IUP Computer Science
CO 310 Fall 1984

Assignment #2
(Due 5 October 1984)


1.  There are two ways to evaluate a polynomial of the form

    P(x) = anxn + an-1xn-1 + . . . + a2x2 + a1x + a0

In the first way, each term is calculated separately and added to a TOTAL.  That is, TOTAL is set to zero, then a0 is added to it, followed by a1x and a2x2 until anxn is added.

In the second way, the polynomial is evaluated using Horner's rule, which considers P(x) as

(...((anx + an-1)x + . . . + a1)x + a0

That is, TOTAL is set to anx, then an-1 is added and the TOTAL is multiplied by x.  This is repeated using an-2 . . . a1 and multiplying by x each time.  Finally, a0 is added.

Write two PASCAL functions to evaluate a polynomial in each of these ways.  The parameters for each function consist of an array, a, of coefficients (to hold a0 thru an), the degree of the polynomial, n, and the point where the evaluation is to be made, x.  The array, a, and x should be REAL; n is INTEGER.

    After writing the functions, show the frequency counts for the each of the statements and state which function evaluates the polynomial more efficiently.  Use frequency counts or computing time to justify your statement.  Note:  you are not being asked to run these functions on the computer; only handwritten functions are required.


2.  If the variables j, k, n, and p are declared as INTEGER, show the frequency counts in terms of n and/or p for each assignment and decision in the following statments.  Note:  both n and p are guaranteed to be even numbers.
     for k := 1 to n do
     begin
          j := 0;
          while j < p do
               j := j + 2;
          j := 0;
          while j < k do
               j := j + 2
     end;

3.  Write a recursive PASCAL function to calculate the greatest common divisor of two integers, m and n which are both greater than zero.  The greatest common divisor (gcd) is the largest integer that can divide evenly into both m and n.  

    The first step in calculating the gcd is to determine which is smaller, m or n.  Let's assume that m is smaller.  The next step is to calculate the remainder, r, when n is divided by m.   If r is zero, then m is the gcd.  If r is not zero, then the gcd of m and n is the same as the gcd of m and r.  Since r < m and m < n, determining their gcd should be easier.  This process of getting the remainder is then repeated, getting the remainder, q, when m is divided by r and the remainder, t, when r is divided by q, etc. until the remainder becomes zero and the gcd is determined (it is the divisor).

    Write a PASCAL program that reads in pairs of integers, uses the recursive PASCAL function to determine the greatest common divisor, and writes the integers and the gcd in the following form
     The greatest common divisor of _____ and _____ is _____
where your program fills in the blanks.

    Your program must calculate and print the gcd for at least five pairs of integers.  You choose the integers and the type of loop to read in successive pairs.