10
\$\begingroup\$

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 \$.

  1. Write an iterative function power1 to compute \$ x^n \$.
  2. 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. $$

  3. 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. $$

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

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

Here's how I solved it:

main.cpp:

#include <cctype>
#include <cmath>
#include <iostream>
#include <limits>
#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<std::streamsize>::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
    if('\n' == std::cin.peek()) std::cin.ignore();
    return std::tolower(std::cin.get());
}

std::string runTest(int8_t x, uint8_t n)
{
    PowerCalculator obj;
    return "power1(" + std::to_string(x) +  ", " + std::to_string(n) + ") = " + std::to_string(obj.power1(x, n)) + " has been solved " + ((obj.power1(x, n) == std::pow(x, n)) ? "correctly." : "incorrectly.")
    + "\nThis took " + std::to_string(obj.getAccumulator()) + " multiplications and " + std::to_string(obj.getRecursions()) + " recursive calls.\n"
    + "power2(" + std::to_string(x) +  ", " + std::to_string(n) + ") = " + std::to_string(obj.power2(x, n)) + " has been solved " + ((obj.power2(x, n) == std::pow(x, n)) ? "correctly." : "incorrectly.")
    + "\nThis took " + std::to_string(obj.getAccumulator()) + " multiplications and " + std::to_string(obj.getRecursions()) + " recursive calls.\n"
    + "power3(" + std::to_string(x) +  ", " + std::to_string(n) + ") = " + std::to_string(obj.power3(x, n)) + " has been solved " + ((obj.power3(x, n) == std::pow(x, n)) ? "correctly." : "incorrectly.")
    + "\nThis took " + std::to_string(obj.getAccumulator()) + " multiplications and " + std::to_string(obj.getRecursions()) + " recursive calls.\n";
}

int main()
{
    std::cout << runTest(3, 32) << std::endl;
    std::cout << runTest(3, 19) << std::endl;

    int8_t x = 0;
    uint8_t n = 0;

    std::cout << "Would you like to run your own calculation (y/N): ";
    while('y' == getSanitizedChar())
    {
        std::cout << "Enter a number for the base: ";
        x = getSanitizedNum();
        std::cout << "Enter a power to raise the base to: ";
        n = getSanitizedNum();

        std::cout << runTest(x, n) << std::endl;

        std::cout << "Run a calculation again (y/N): ";  // signify n as default with capital letter
    }
}

PowerCalculator.h:

#ifndef POWERCALCULATOR_H
#define POWERCALCULATOR_H

#include <cstdint>

class PowerCalculator
{
public:
    int64_t power1(int8_t, uint8_t);
    int64_t power2(int8_t, uint8_t);
    int64_t power3(int8_t, uint8_t);
    void setAccumulator(unsigned);
    unsigned getAccumulator();
    void setRecursions(unsigned);
    unsigned getRecursions();
private:
    unsigned accumulator = 0;
    unsigned recursions = 0;
};

#endif

PowerCalculator.cpp:

#include "PowerCalculator.h"

void PowerCalculator::setAccumulator(unsigned num)
{
    accumulator = num;
}

unsigned PowerCalculator::getAccumulator()
{
    return accumulator;
}

void PowerCalculator::setRecursions(unsigned num)
{
    recursions = num;
}

unsigned PowerCalculator::getRecursions()
{
    return recursions;
}

int64_t PowerCalculator::power1(int8_t base, uint8_t power)
{
    int64_t product = 1;
    for(size_t i = 0; i < power; ++i)
    {
        ++accumulator;
        product *= base;
    }
    return product;
}

int64_t PowerCalculator::power2(int8_t base, uint8_t power)
{
    ++recursions;
    if (0 == power) return 1;
    else
    {
        ++accumulator;
        return base * power2(base, power - 1);
    }
}

int64_t PowerCalculator::power3(int8_t base, uint8_t power)
{
    ++recursions;
    if (0 == power) return 1;
    else if (0 == (power % 2))
    {
        ++accumulator;
        return power3(base, power/2) * power3(base, power/2);
    }
    else
    {
        ++accumulator;
        return base * power3(base, power/2) * power3(base, power/2);
    }
}

CMakeLists.txt:

cmake_minimum_required(VERSION 2.8.7)
project(Project1)

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Werror -Wall -Wextra -pedantic-errors -Wformat=2 -Wno-import -Wmain -Wchar-subscripts -Wsequence-point -Wmissing-braces -Wparentheses -Winit-self -Wswitch-enum -Wstrict-aliasing=2 -Wundef -Wshadow -Wpointer-arith -Wcast-qual -Wcast-align -Wwrite-strings -Wredundant-decls -Winline -Wdisabled-optimization -Wunused-macros -Wno-unused -std=c++11")

file(GLOB_RECURSE sources ${PROJECT_SOURCE_DIR}/src/*.cpp)
add_executable(Project1 ${sources})

Please feel free to comment on any aspect of the code.

\$\endgroup\$

4 Answers 4

5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

You could DRY this up:

{
    ++accumulator;
    return power3(base, power/2) * power3(base, power/2);
}
else
{
    ++accumulator;
    return base * power3(base, power/2) * power3(base, power/2);
}

Bit too much repeated code for my taste. Put some in a function with a "Name"

Why is '\n' special?

// absorb newline character (if existant) from previous input
if('\n' == std::cin.peek()) std::cin.ignore();
return std::tolower(std::cin.get());

I would think all white space is the same? In which case you can use operator>> which ignores space.

int char;
std::cin >> char;

Why do you use a different technique for numbers and char during sensitization. You could templateize the function and use the same code.

tamplte<typename T>
T getSanitizedNum()
{
    // static_assert(some numeric type);


    T    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<std::streamsize>::max(), '\n');
        std::cout << "Invalid input.  " << ErrorData<T>::message;
    }
    return input;
}
\$\endgroup\$
2
\$\begingroup\$

Your implementation of power3() is inefficient, as it contains a common subexpression power3(base, power/2) that is costly to compute.

\$\endgroup\$
2
\$\begingroup\$

Judging from the low readability of runTest(), you may benefit from having a separate testing file, allowing you to improve the readability in some way. It may also allow for additional tests, and you can then provide names for each test (the user may want to know what kinds of tests are available).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.