Knowledge is power

Resurrecting my C++ saga, I was given this project for my CS2 class:


This problem considers several ways to compute \$ x^n \$ for some \$ n
\ge 0 \$.

• Write an iterative function power1 to compute \$ x^n \$.

-
Write a recursive function power2 to compute \$ x^n \$ using the following
recursive definition:


$$
x^n = \left\{ \begin{array}{ll}
1 & \mbox{if}\ n = 0 \\
x \times x^{n - 1} & \mbox{if}\ n > 0
\end{array}
\right.
$$

-
Write a recursive function power3 to compute \$ x^n \$ using the following
recursive definition:


$$
x^n = \left\{ \begin{array}{ll}
1 & \mbox{if}\ n = 0 \\
(x^{n / 2})^2 & \mbox{if}\ n\ \mbox{is even} \\
x \times (x^{n/2})^2 & \mbox{if}\ n\ \mbox{is odd}
\end{array}
\right.
$$

-
How many multiplications will each of the functions power1, power2,
and power3 perform when computing \$ 3^{32} \$? \$ 3^{19} \$?

• How many recursive calls will power2 and power3 make when computing \$ 3^{32} \$? \$ 3^{19} \$?

Here's how I solved it:

main.cpp:

```
#include
#include
#include
#include
#include "PowerCalculator.h"

/**
* Makes sure data isn't malicious, and signals user to re-enter proper data if invalid
*/
unsigned getSanitizedNum()
{
unsigned input = 0;
while(!(std::cin >> input))
{
// clear the error flag that was set so that future I/O operations will work correctly
std::cin.clear();
// skips to the next newline
std::cin.ignore(std::numeric_limits::max(), '\n');
std::cout << "Invalid input. Please enter a positive number: ";
}
return input;
}

/**
* Safetly grabs and returns a lowercase version of the character (if the lowercase exists)
*/
char getSanitizedChar()
{
// absorb newline character (if existant) from previous input

Good call using 64-bit ints for output.

Don't use eight bit ints for inputs. I'd use a plain int without specifying length. Note that a 32-bit int value to the second power will fit into 64 bits, and zero or one to the 0x7fffffff (0xffffffff for unsigned) power will also.

@200_success mentioned eliminating duplicate power3(base, power/2). That's a great suggestion. power3 may be rewritten as:

int64_t PowerCalculator::power3(int base, unsigned int power)
{
    ++recursions;
    if (0 == power) return 1;

    ++accumulator;
    int64_t result = power3(base, power/2);
    result *= result;

    if (1 == (power % 2))
        result *= base;

    return result;
}

Your runTest() is verbose and not very readable with all those to_string(), and you've got lots and lots of string copying.

Consider using std::ostringstream and then returning the string it creates. It will be more concise and more efficient.

A little perspective, which may be useful - the string formatting (allocation, deallocation, copying) you're doing costs you thousands of times more cycles than computing the powers.

StackExchange Code Review Q#78790, answer score: 5