APCS Workshop, Third Day

Introduction

The version of the class provided online in bigint.h has division and modulus operators implemented. These are not implemented in the class discussed in the case study so that teachers can make division a class project. However, the version provided here is also available online --- see the college board web page for details)

(http://cbweb1.collegeboard.org/ap/computer-science/html/indx001.html)

Group Activity

1. The program fact.cpp shows a simple use of the BigInt class to compute factorials. The first group exercise is to reason about a run of this program that shows the output of all constructors that are called as well as destructors. Note that in the implementation in the case study there is no reason for a destructor since there's no dynamic memory allocated in the class. The output below was generated by including a destructor to help reason about what temporary variables are created during the process of computing factorials.

   To determine the cause of each line of output you'll need to look both at the factorial program fact.cpp and at the implementation of the BigInt class in bigint.cpp. You should describe, for each constructor and destructor, the cause of the output. For example, the first line of output, "default constructor called" is caused by the definition of the variable answer in main.

   User-entered input is in italics

   	prompt> fact
   	default constructor called
   	fact up to: 3
   	int constructor called num = 1
   	copy constructor called with 1
   	destructor called for 1
   	destructor called for 1
   	0! = 1
   	int constructor called num = 1
   	copy constructor called with 1
   	destructor called for 1
   	destructor called for 1
   	1! = 1
   	int constructor called num = 1
   	copy constructor called with 2
   	destructor called for 2
   	destructor called for 2
   	2! = 2
   	int constructor called num = 1
   	copy constructor called with 6
   	destructor called for 6
   	destructor called for 6
   	3! = 6
   	destructor called for 6
   

2. If that was not challenging enough consider the run below showing part of a run for both 10! and 11!. There's a big difference between these two because operator *= is defined for both BigInts and ints. The BigInt version is called only when a factorial over 10 is calculated. You should reason about why each of the lines of output appears for the run shown below.

   	9! = 362880
   	int constructor called num = 1
   	copy constructor called with 3628800
   	destructor called for 3628800
   	destructor called for 3628800
   	10! = 3628800
   	int constructor called num = 1
   	int constructor called num = 11
   	copy constructor called with 3628800
   	int constructor called num = 0
   	copy constructor called with 3628800
   	copy constructor called with 3628800
   	destructor called for 3628800
   	destructor called for 3628800
   	copy constructor called with 36288000
   	copy constructor called with 36288000
   	destructor called for 36288000
   	destructor called for 36288000
   	destructor called for 39916800
   	destructor called for 362880000
   	destructor called for 11
   	copy constructor called with 39916800
   	destructor called for 39916800
   	destructor called for 39916800
   	11! = 39916800
   
   

3. There is no post-increment operator implemented for the BigInt class. The correct prototype for one is shown below. Implement the body of the function. You'll probably need three statements for this, you should use the overloaded operator +=. (Note that the int parameter is a dummy parameter that's not used, it just serves to differentiate the overloaded postincrement ++ from a preincrement ++). BigInt BigInt::operator ++(int)

4. show-meWrite an implementation of division in line with the AP exam question from this year (1997). The question asked that a division algorithm be implemented that uses the following pseudocode (verbatim)

      copy the dividend to tempDiv 
      set quotient to zero
      while tempDiv >= divisor
           subtract divisor from tempDiv
           increment quotient by one
   

   Use this to implement the member function whose header is given below. For this problem assume that divisor and dividend are both positive (as with the AP test question).

        BigInt & BigInt::operator /=(const BigInt & rhs)
       // postcondition: return BigInt / rhs after modification
   

Lab Activity

1. Using the SysTimer class declared in systimer.h determine, empirically, the time needed to square an N-digit BigInt, where N varies from 0 to 900 in increments of 100. Make the N-digit number all 9's for a good upper bound. You can construct such a BigInt from a string formed by concatenating 9's together. Output might be similar to the following (from a Pentium 133 running Turbo 4.5). You can determine the number of digits in a BigInt by using the ToString member function (then using length).

   	#dig	^2 dig	time
   	0	1	0
   	100	200	0.11
   	200	400	0.5
   	300	600	1.16
   	400	800	2.09
   	500	1000	3.3
   	600	1200	4.84
   	700	1400	6.48
   	800	1600	8.46
   	900	1800	10.66
   

2. Write a program that combines the timing idea above, and the number of digits, with the Factorial function from fact.cpp. Generate all factorials between 1 and a user-entered number printing the number of digits in each factorial and the time needed to compute the factorials.

3. The hailstone sequence is formed by using the following iterative technique for a number n: int f(int n) { if (n % 2 == 0) return n/2; else return 3*n + 1; } while (n != 1) { n = f(n); } It is conjectured, though unproven, that this loop always terminates. Write a program to find the BigInt value N that yields the longest hailstone sequence. Limit the search between two user-entered values.

4. Write both a logarithmic and a linear function for raising a BigInt to an integer power (i.e, one function is O(log n) and the other is O(n) for the number of multiplies needed to compute b^n). Time these functions and see if the empirical times match the analytical runtimes (they won't match, why?)

Lunch

Group Activity

1. What classes should be used and talked about in conducting workshops. How should classes be used in conjunction with discussing syntax/language issues?

2. How much time should be spent on environment issues, e.g., using an IDE, using projects, compiler quirks, etc. ?

3. How can BigInt be used to introduce C++, how much time should be spent on BigInt when conducting workshops?

4. What ideas and concepts do you anticipate causing problems or being difficult in teaching the course to students and in conducting workshops?

5. What books are appropriate, what resources are needed, and where should teachers look for more information?

Lab Activity