Your goal for this lab is to experiment with different implementations of the NaturalNumber kernel and of the power function and compare their performance. In particular, you will use two implementations of the NaturalNumber kernel (NaturalNumber1L and NaturalNumber2) and the two implementations of the power method you have encountered before (a slow, iterative one and a fast recursive one). So while comparing the various observed timing functions, remember that you are trying to understand how each implementation impacts the performance of the code being timed and what other factors affect the execution time.
Follow these steps to set up a project for this lab.
Take a look at the code provided. Note the following:
Make sure you understand what the main method does.
Run the program and enter 7 as the value of n. You can copy and paste the output data to a text file to save it. You can easily create a file in the data folder in your project by right-clicking on the data folder in the Package Explorer view and selecting New > File.
You can plot the data (the power p along the x axis and the time along the y axis) by hand, but it is more convenient to use a spreadsheet program such as Microsoft Excel. If you are using your own computer and do not have such a program, you should use (share) one of the computers in the lab for this activity. On the lab computers, you can find Excel in the Start Menu.
Here are some brief instructions on how to use Excel. If you have never used a spreadsheet application before and are having problems, just ask one of the instructors for help.
| Task | Instructions |
|---|---|
| Enter Data | Copy the output of the program (except the first input line) to the clipboard; click on cell A1 in a clear worksheet and then click on the small down arrow below the Paste button in the top-left corner of the window and select Paste Special.... (Don't click the Paste button itself because it will paste all the data in one column.) In the window that pops up, select Text (not HTML or Unicode Text) and click OK. |
| Generate Chart | Select all the cells you pasted (including the column labels). Click on the Insert tab at the top of the window. In the Ribbon toolbar, under Charts, find the Insert Scatter icon, click on it, and select the Scatter with Smooth Lines icon. A chart of your data should be displayed. |
| Extend Chart | If you paste a new column of data (times) to the right of the last column (e.g., paste the timings for a different value of n and the same values for p in column C), you can include the new data in the same chart by clicking in the chart, this will highlight the cells containing the data displayed in the chart. Then drag the bottom right corner of the box around the displayed data to include the new column. That's it! The chart should now display the new data. If this does not work, you can just select all the data and follow the steps above to create a new chart. |
Now that we have a chart of the execution time for the fast power using NaturalNumber1L, let's time the same fast implementation of power using a different implementation of the kernel, NaturalNumber2. Copy NaturalNumber1LFastPower.java to NaturalNumber2FastPower.java. Open NaturalNumber2FastPower.java in the editor and replace extends NaturalNumber1L in the first line of the class with extends NaturalNumber2. This way you will now time the fast power using NaturalNumber2 instead of NaturalNumber1L. To be sure, double check in the main method that n is instantiated with NaturalNumber2FastPower's constructor.
Run the NaturalNumber2FastPower program and again enter 7 as the value of n. You can save your output to the same file or a new file. In any case, copy and paste the new data in the spreadsheet. Since the first column lists the same values of the power p as for the previous timing experiment, you should only paste the column of time data in column C of the spreadsheet. This can be accomplished by pasting the new data in columns C and D and then deleting column C (right-click on the header of column C—the cell labeled C—and select Delete or Delete Columns from the drop-down menu). Then follow the instructions above to either extend the chart to include the new data or to create a new chart with both timing functions. You may want to rename the two labels "t" to something like "t1L" and "t2" so that it will be easy to distinguish them in the chart.
Compare the two timing functions and discuss with a classmate what you observe.
Copy NaturalNumber2FastPower.java to NaturalNumber2SlowPower.java. Open NaturalNumber2SlowPower.java in the editor and paste the following method above the main method. Note that this is an instance method and the number being raised to the p power is called this. This implementation overrides the one inherited from NaturalNumber2 and it is the one that will be timed here. To be sure, double check in the main method that n is instantiated with NaturalNumber2SlowPower's constructor. Also observe that the code of the slow power uses the newInstance method whenever it needs to create a new NaturalNumber object and this way it guarantees that all the NaturalNumber objects will be of dynamic type NaturalNumber2SlowPower.
Run the NaturalNumber2SlowPower program and again enter 7 as the value of n. You can save your output to the same file or a new file. In any case, copy and paste the new data in the spreadsheet so that you have three columns: the column of the power values p, the column of the times for the fast power t2 fast, and the column of the times for the slow power t2 slow.
Create a chart to compare the two timing functions. Compare them and discuss with a classmate what you observe.
Now run again NaturalNumber2FastPower and NaturalNumber2SlowPower and use a 2-digit value for n, e.g., 19. Generate a new chart to compare these results. How do these timing functions compare to the timing functions for the fast and slow implementation of power using n = 7? You may want to generate a chart with all four timing functions to make a direct comparison.
Depending on the speed of the computer you are using (and how patient you are), you may want to try with bigger values of n, say three digits, and then possibly four or more. Can you predict with any confidence what kind of execution times you should expect based on the performance behavior you have observed for smaller values of n?
There are other dimensions along which to explore and compare the performance of the fast and slow implementations of power. Here are some other possibilities: