CSE 221 Lab 7

Table of Contents

Objectives

The Problem

Your boss has tasked you to implement a Power operation which will be used later in the company's new calculator, the TA-8500. The TA-8500 represents numbers as objects of type Natural_Number for its operations (add, subtract, power, etc.). ( In the next assignment, you will implement the Root operation.)

You will actually provide three different implementations of Power and you will (crudely) time the difference in performance between two of the implementations. The second and third implementations will be done by making Power an extension of Natural_Number_1_C, and these are the two implementations whose performance you will compare.

Set Up

  1. In an xterm window, create a new directory (folder) for this lab by typing the "make directory" command: 
         mkdir lab07
  2. Change or move to the new directory (folder) for this lab by typing the "change directory" command: 
         cd lab07
  3. Copy the catalog for this lab by typing the "copy" command: 
        cp -R /class/sce/now/221/labs/catalogs/lab07/* .
    NOTE: The period . is part of the command. It denotes the current directory (folder).

    This copy command will copy recursively (because of the -R) all the files and directories from the shared class directory into your directory, effectively duplicating the entire substructure from the class directory into your directory.



  4. To see what was copied, type the "list" command: 
         ls
    You should see

    In the directories AI and CI, you will see a Natural subdirectory. Within AI/Natural you will see one file: Power.h, and within CI/Natural you will see two files: Power_1.h and Power_2.h.

Method

Implementation 1 - Adding Power as a global operation

  1. Examine the file Power_Test.cpp, which is a simple test driver for global_procedure Power specified below. (Note that, 0^0 = 1.)
      2. global_procedure Power (
        alters Natural_Number_1_C& n,
        preserves Integer p
    );
/*!
    requires
        p >= 0
    ensures
        n = #n ^ (p)
!*/

     
  2. Write a body for the Power operation which uses the "obvious" algorithm -- repeated multiplication by the original n. This body goes into Power_Test.cpp.

    3.  
  3. Test the above implementation, revising as necessary until you're convinced that this implementation of Power works. For implementation 1, the grader will look at the source code and output of Power_Test.

Implementation 2 - Making Power an extension

  1. Examine the file Power_1_Test.cpp, which is the same simple test driver as above but this time for Power being the extension in abstract_instance class Natural_Power, which is in the file AI/Natural/Power.h in your lab07 directory.

    2.  
  2. Write a body for the Power operation in the file CI/Natural/Power_1.h in your lab07 directory. DO NOT write the body in the test driver. Use the "obvious" algorithm (repeated multiplication). This should be very straightforward, it is almost a cut and paste from implementation 1!

    3.  
  3. Test Natural_Power_1::Power using Power_1_Test.cpp as the test driver. Revise the operation body for Power until you're convinced that it works. The grader will look at the source code of Power_1.h and the output for Power_1_Test to grade this part.

Implementation 3 - Making Power more efficient

  1. Copy Power_1_Test.cpp to Power_2_Test.cpp, and make the new test driver use a new implementation of Power simply by replacing ALL occurrences of Power_1, in Power_2_Test.cpp, with Power_2.

    2.  
  2. Provide a new body for the Power operation in the file CI/Natural/Power_2.h in your lab07 directory. This time use the more efficient and non-obvious "fast powering" method discussed in class.

    3.  
  3. Test Natural_Power_2::Power using Power_2_Test.cpp as the test driver and revising the operation body as necessary until you're convinced that this implementation of Power also works. The grader will look at the source code of Power_2.h and the output for Power_2_Test to grade implementation 3.

Timing

This part will be up to you to flesh out. The idea is to run both Power_1_Test and Power_2_Test that use two different implementations of Power. Come up with some way of reporting which version of Power is faster and by how much. There is a UNIX command available called "time" which you can use for this purpose. It can be executed with the command: 
/bin/time Power_Test
where Power_Test is the name of your executable program. After the program executes, the time command will produce output similar to: 
real   24.7
user    3.0
sys     0.0
This indicates that the program spent 3.0 seconds on behalf of the user (this is the amount of time the computer spent executing user code), 0.0 seconds on system time (this is time spent executing UNIX kernel routines) and a total of 24.7 seconds to run the entire program. For comparing the performance of Power_1 vs. Power_2, it's good enough to just compare the "user" times, since this represents how much time the computer worked on your behalf.

Report your timing data in a separate text file called TIMING-REPORT.txt and make sure this file is located in your lab07 directory .

VERY IMPORTANT NOTE

A correct body for Natural_Power_2::Power will be made available at 4pm Monday after the submission deadline. Thus, late submissions for lab 7 will NOT be accepted after 4:00 pm, Monday.

What To Turn In

Use the rcpp-submit command to turn in: Make sure you are in your lab07 directory. Then the rcpp-submit command for this lab assignment is: 
rcpp-submit c221xx lab07
where "xx" is to be replaced by lower case letters designating your section (see the course home page for a list).

Want To Do More?

Here are some possibilities: Any extra work is strictly optional, for your own benefit, and will not directly affect your grade.