Description
The purpose of the first programming exercise is to familiarize you with the programming standards and coding conventions that are required for this course. All students taking this course are expected to have a certain level of proficiency which includes the ability to read and understand code written by others. Students are also expected to write code that efficiently implements and tests various algorithms using programming constructs studied in your programming classes and functions whose syntaxes and usage information you can find in ANSI/ISO C++ 11 language documentation.
In this exercise and all subsequent programming projects, you will be expected to properly document your code using the coding conventions for this course, program in multiple files so that there is a wall between the public interface and implementation of your algorithms as well as the application that uses the implementation. This assignment will test your ability to follow this approach to programming no matter what IDE (integrated development environment) that you use to write your code. Your code will be tested using ANSI/ISO C++ 11.
Definition 1. Empirical algorithmics is a computer science area of specialization that involves the use of experimental and statistical, rather than theoretical, methods to analyze the behavior of algorithms.
The goals of empirical algorithmics are characterization of an algorithm based on its performance, enhancing the performance of an algorithm using empirical techniques and the comparative analysis of the various algorithms that solve the same problem within a given context.
Definition 2. A power is an exponent to which a given quantity is raised. The expression xn is therefore known as “x to the nth power.” The computation of powers arise in many numerical algorithms.
You will write code to empirically compare the performance of a naive and the fast algorithms for computing powers of positive big integer values where the exponent is a non-negative integer. Here is the pseudocode for a naive power algorithm,
Listing 1: Naive Power Algorithm
ALGORITHM: NAIVE-POWER(x,n)
{Input: n – a non-negative integer x – a positive integer Output: xn
}
if n = 0 or x = 1
return 1
endif
y ← 1
for i ←1 to n stepSize ← 1
y ←y× x
endfor
return y
endAlgorithm
The power of a number can be determined more efficiently using a successive squaring algorithm.
Here is a pseudocode description of the algorithm.
Listing 2: Fast Power Algorithm
ALGORITHM: FAST-POWER(x,n)
{Input: n – a non-negative integer x – a positive integer Output: xn
}
if n = 0 or x = 1 return 1
endif y ← 1
while n > 1
if n mod 2 = 0
n ← n / 2
else
y ← y × x n ← (n – 1) / 2
endif
x ← x × x
endwhile
return y × x endAlgorithm
I have provided BigInt.h a header file that contains prototypes for functions of a “Big Integer” library. I have also provided BigInt.cpp the implementation file for the header file. These files allow for representing very large integers and performing basic arithmetic operations on them. Do not make any changes to these files.
The BigMath Header File
Complete the implementation of BigMath.h so that it contains implementations for the naive and fast exponentiation algorithms.
The PowerAnalyzer Program
The PowerAnalyzer.cpp file will consist of only one function, the main. The main function will perform the following tasks:
- It prompts the user to enter the base of a power.
- It prompts the user to enter the exponent of a power.
- It computes the powers using both the fast and naive algorithms and displays the powers.
- It randomly generates a four-digit positive integer for the base of a power.
- It randomly generates a two-digit positive integer for the exponent of a power.
- Similarly, it computes the powers using these randomly generated integers and both the fast and naive algorithms and displays the powers.
- It prompts the user for a positive integer to be used as the base in measuring and displaying runtimes for generating various powers of the base.
- For n = {16,32,64,128,256,512,1024,2048,4096,8192}, your program will compute, using the naive and fast exponentiation algorithms, powers of the base entered by the user and measure and display the execution times in nanoseconds for these algorithms as shown in the table in the sample run.
