CS 24, Fall 2016

Programming Assignment 5

Due: Friday, November 18, 11:59pm
Worth: 100 points

PA5 can be done either in two-people teams or individually.

If you are working with a partner, be sure that both partners' names are in a comment at the top of the source code file, and that you properly form a group for this project in the submit.cs system.

This assignment is all about practice writing recursive functions. Therefore, your solutions must be recursive, and we will check the source code to make sure they are. If any of your solutions does not use recursion, then zero points will be awarded for it, not the submit.cs score. The skeleton file from part 1, and the 5 executable solutions are available in ~cs24/pa5/ - you should run the solutions, and your programs should match their behaviors. Here are some sample runs: power1 and power2, reduce, sqroot, say.

1. [30 points] Implement two versions of a function, power(x,n) that computes xⁿ where x is a double value, and n is an int that is greater than or equal to 0.
   1. Complete power1.cpp by implementing power as a recursive function that employs these truths:
      • power(x,0) = 1.0
      • power(x,1) = x
      • power(x,n) = x * power(x, n-1)
      Leave the variable named call_count alone, so the program will count and print the number of times your function is called. This number must exactly match our solution's count to earn any credit from submit.cs tests.
   2. Write an improved version of the power program, in a file called power2.cpp, by starting with a copy of power1.cpp. The only difference should be the power function itself. Use the following algorithm (quoted from Data Structures, Algorithms & Software Principles in C, by Thomas A. Standish) "that works by breaking n down into halves (where half of n = n/2), squaring power(x,n/2), and multiplying by x again if n was odd. For example, x¹¹ = (x⁵)*(x⁵)*x, whereas x¹⁰ = (x⁵)*(x⁵)." Use the same base cases as power1. Again your call counts must match our solution to earn credit.
2. [20 points] Write a program named reduce.cpp to reduce a fraction entered on the command line to its simplest form.
• Write and use a recursive function named gcd that takes two positive int arguments, m and n, and returns the greatest common divisor of m and n. Use Euclid's algorithm as explained here by Prof. Standish in the same text cited above:

  "According to Euclid's algorithm for finding the greatest common divisor, gcd(m,n), of two positive integers m and n, one can take successive pairs of remainders, and when one of the remainders is zero, the other number in the pair is the gcd. Letting (m,n) be the first remainder pair, we can write m = q * n + r, such that 0 ≤ r < n. Here, q is the quotient of m upon division by n (q = m / n), and r is the remainder of m after division by n (r = m % n). Any divisor (including the gcd) that divides m and n must also divide r, since r = m - q * n. Consequently the gcd of m and n must be the same as gcd(n,r). In Euclid's algorithm, one starts with the pair (m,n) and computes the pair (n,r). Then, if r = 0, the gcd(m,n) = gcd(n,r) = n. But if r ≠ 0, the pair (n,r) is replaced by the next successive remainder pair, which is guaranteed to have the same gcd."

  There is no need to count the number of times the function is called.
• Write main to extract a fraction from the first two command line arguments as numerator followed by denominator. Use gcd to find the greatest common divisor of the numerator and denominator, and use this divisor to reduce the fraction. The sign of the reduced fraction must be correct. Match the output of our solution, including the handling of usage errors. You may assume the user will never enter 0 as the denominator.
3. [20 points] Write a program named sqroot.cpp to compute the square roots of an unlimited number of non-negative double values entered as command line arguments. This problem requires you to write one recursive function named newton, one auxiliary function named sqroot that calls newton properly, and a main function that will call sqroot.
   • #include <cfloat> to access the constant FLT_EPSILON that should be used as a measure of successive improvement (the value of epsilon in the algorithm description below), and #include <cmath> to use the fabs function (the absolute value function for floating point values).
   • Write function newton to take two double values, x and a, and return the double value that best approximates the square root of x. Use Newton's Method, described once more by Prof. Standish:

     "If |a*a - x| ≤ epsilon, we stop with the result a. Otherwise we replace a with the next approximation, defined by (a + x/a)/2. Then, we test this next approximation to see if it is close enough and we stop if it is. In general, we keep on computing and testing successive approximations until we find one close enough to stop."

   • Write function sqroot to take one double argument, x. This auxiliary function simply makes the initial call to newton with an initial approximation equal to x/2, and returns the result of that function call.
   • main must extract as many numbers as the user types on the command line. For each valid entry, invoke the square root function and print results. Negative values are not valid. Match the output of our solution, including the handling of usage errors - note the program does not stop processing if it encounters a bad argument.
4. [30 points] Write say.cpp, a program to print the English translation of non-negative integers entered on the command line. You should include a recursive function, printEnglish(int n), that calls itself for values greater than 1,000. (In fact our solution calls itself up to four times, depending on the size of its parameter's value.)
   • main must extract as many numbers as the user types on the command line. For each valid entry, invoke printEnglish to print results. Negative values are not valid.
   • Match the output of our solution, including the handling of usage errors - note the program does not stop processing if it encounters a bad argument. IMPORTANT: every number printed by printEnglish (except the special case of zero) is followed by a single space at the end of the line.
   • Here are some useful strings and constants from our say.cpp solution. You may copy and paste them into your solution if you want.
5. Submit all five programs for project PA5 at https://submit.cs.ucsb.edu/, or use the following command from a CS terminal:

   ~submit/submit -p 595 power1.cpp power2.cpp reduce.cpp say.cpp sqroot.cpp

   If you score 100/100 and you've followed all of the other rules, then you'll earn full credit.

---

Updated 11/5/2016, by C. Michael Costanzo.