Computing the Ackermann Function

Question

How can I improve this code? It computes the Ackermann function as long as m<4 and n<13.

#include <iostream>
#include <limits>

// Ackermann function calculations
unsigned int ackermann(unsigned int m, unsigned int n){
    if(m == 0)
        return n+1;
    if(n == 0)
        return ackermann(m-1,1);
    return ackermann(m-1,ackermann(m,n-1));
}

// Check for non-integer input
bool inputCheck(){
    if(!std::cin.fail())
        return false;

    std::cout << "Invalid input!" << std::endl;
    return true;
}

// Check for negative or overflow errors
bool numCheck(int i, char name){
    if(i < 0){
        std::cout << "Negative error!" << std::endl;
        return true;
    }

    if(name == 'm' && i > 3){
        std::cout << "Overflow error (m > 3)!" << std::endl;
        return true;
    }

    if(name == 'n' && i > 12){
        std::cout << "Overflow error (n > 12)!" << std::endl;
        return true;
    }

    return false;
}

// Run input and num checks
bool check(int x, char y){
    bool result = inputCheck() || numCheck(x, y);

    std::cin.clear();
    std::cin.ignore();

    return result;
}

int main(){

    int m, n;
    bool valM, valN;

    do{
        std::cout << "m = ";
        std::cin >> m;
        valM = check(m, 'm');
    } while(valM);

    do{
        std::cout << "n = ";
        std::cin >> n;
        valN = check(n, 'n');
    } while(valN);

    std::cout << "\nM = " << m << "\nN = " << n
            << "\n\nCALCULATING..." << std::endl;

    std::cout << "A(" << m << ',' << n << ") = "
            << ackermann(m,n) << std::endl;

    return 0;
}

A majority of the code is for detecting errors (such as invalid or negative input) and for preventing overflow errors (such as Ackermann(4,2)). A minority of the code actually calculates the Ackermann function.

Answer 1

bool inputCheck(){
    if(!std::cin.fail())
        return false;

    std::cout << "Invalid input!" << std::endl;
    return true;
}

Carefully name your functions with a meaningful name. inputCheck doesn't really tell anyone what to expect as a result.

Prefer to distinguish language constructs with spaces.

You can use the contextual boolean conversion operator to check the if the stream has failed rather than explicitly calling !std::cin.fail().

Prefer to avoid std::endl. Be aware of what the manipulator std::endl actually does. Stream '\n' as it explicitly states your intent, correctly outputs the end-of-line character, and is shorter to type.

bool isInvalidInput() {
    if (std::cin) {
        return false;
    }
    std::cout << "Invalid input!\n";
    return true;
}

---

bool numCheck(int i, char name){
    if(i < 0){ /* ... */ }
    if(name == 'm' && i > 3){ /* ... */ }
    if(name == 'n' && i > 12){ /* ... */ }
    return false;
}

Specify const for immutable variables. const self-documents that a variable should not change values in the current scope and any accidental modification to the value is detected at compile time rather than run time.

Prefer enumerations to represent sets of related named constants.

Avoid magic constants as they are difficult to understand and may be overlooked. Prefer symbolic constants to give values contextual meaning.

---

bool check(int x, char y){
    bool result = inputCheck() || numCheck(x, y);
    std::cin.clear();
    std::cin.ignore();
    return result;
}

Do you really want to ignore the remaining buffer on success?

---

unsigned int ackermann(unsigned int m, unsigned int n){
    if(m == 0)
        return n+1;
    if(n == 0)
        return ackermann(m-1,1);
    return ackermann(m-1,ackermann(m,n-1));
}

The Ackermann–Péter function should be tail-call optimized by any decent compiler, so you won't find much improvement with the recursive approach. If you really care for performance, calculate Ackerman values in constant time using the formula's for \$A(m,n)\$.

$$ A(0,n) = n + 1\\ A(1,n) = n + 2\\ A(2,n) = 2n + 3\\ A(3,n) = 2^{(n+3)} - 3\\ A(4,0) = 13\\ A(4,1) = A(5,0) = 65533 $$

---

Contractually enforce your preconditions by testing them in the function that requires them.

namespace impl {
    unsigned Ackermann(unsigned m, unsigned n) {
        // calculate A(m,n)
    }
    void check_overflow_bounds(unsigned m, unsigned n) {
        if (m > 3 || n > 12) {
            throw std::out_of_bounds("");
        }
    }
}
unsigned Ackermann(unsigned m, unsigned n) {
    impl::check_overflow_bounds(m, n);
    return impl::Ackermann(m, n);
}

If your return type is an unsigned int, will Ackermann values overflow if \$m < 4\$ and \$n = 13\$? Are there Ackermann values that don't overflow when \$m = 4\$ or \$m = 5\$? Consider what actually is computable and throw an overflow exception for values that are not computable.

Answer 2

The first thing that struck me when I looked at your code was that you had almost identical code to get user input for m and n.

When you think of what you are trying to in such blocks of code a bit carefully, you can easily transform them into functions and can be reused.

Instead of

  bool valM, valN;
  do{
  std::cout << "m = ";
  std::cin >> m;
  valM = check(m, 'm');
  } while(valM);

Use

 int m = getInput("m = ", 'm');

However, you have some hard coded logic that assumes that the maximum value of m is 3. You can remove the card coded magic number and let it be an input to getInput.

 int m = getInput("m = ", 'm', 3);

The signature of getInput is:

int getInput(std::string const& prompt,
             char name,
             int max);

I have the following suggested implementation of getInput. It follows your ideas but expresses the intent of what are trying to do more clearly, IMHO.

int getInput(std::string const& prompt,
             char name,
             int max)
{
   int num = 0;
   while ( true )
   {
      std::cout << prompt;
      std::cin >> num;
      if ( isValidValue(num, max) )
      {
         break;
      }
      printErrorMessage(name, num, max);
   }

   return num;
}

isValidValue is simple to implement given the inputs.

bool isValidValue(int num, int max)
{
   return ( num >= 0 && num <= max );
}

printErrorMessage is not that difficult either.

void printErrorMessage(char name, int num, int max)
{
   if (num < 0)
   {
      std::cout << "Negative error!" << std::endl;
   }

   if ( num > max )
   {
      std::cout << "Overflow error. (" << name << " > " << max << ")!" << std::endl;
   }
}

I would suggest dividing getInput further into two functions -- one function that gets the raw input and let getInput perform the error checks before returning a valid input.

int getRawInput(std::string const& prompt)
{
   int num = 0;
   std::cout << prompt;
   std::cin >> num;
   return num;
}

int getInput(std::string const& prompt,
             char name,
             int max)
{
   int num = 0;
   while ( true )
   {
      num = getRawInput(prompt);
      if ( isValidValue(num, max) )
      {
         break;
      }
      printErrorMessage(name, num, max);
   }

   return num;
}

In the event that you need to get multiple types of raw input, such as ints and doubles, it can be easily converted to a function template.

template <typename T>
T getRawInput(std::string const& prompt)
{
   T t = {};
   std::cout << prompt;
   std::cin >> t;
   return t;
}

---

Here's the complete program that incorporates my suggestions. It works on my computer as you would expect with the limited amount of testing I subjected it to.

#include <iostream>
#include <limits>

// Ackermann function calculations
unsigned int ackermann(unsigned int m, unsigned int n){
   if(m == 0)
      return n+1;
   if(n == 0)
      return ackermann(m-1,1);
   return ackermann(m-1,ackermann(m,n-1));
}

bool isValidValue(int num, int max)
{
   return ( num >= 0 && num <= max );
}

void printErrorMessage(char name, int num, int max)
{
   if (num < 0)
   {
      std::cout << "Negative error!" << std::endl;
   }

   if ( num > max )
   {
      std::cout << "Overflow error. (" << name << " > " << max << ")!" << std::endl;
   }
}

template <typename T>
T getRawInput(std::string const& prompt)
{
   T t = {};
   std::cout << prompt;
   std::cin >> t;
   return t;
}

int getInput(std::string const& prompt,
             char name,
             int max)
{
   int num = 0;
   while ( true )
   {
      num = getRawInput<int>(prompt);
      if ( isValidValue(num, max) )
      {
         break;
      }
      printErrorMessage(name, num, max);
   }

   return num;
}

int main(){

   int m = getInput("m = ", 'm', 3);
   int n = getInput("n = ", 'n', 12);

   std::cout << "\nM = " << m << "\nN = " << n
      << "\n\nCALCULATING..." << std::endl;

   std::cout << "A(" << m << ',' << n << ") = "
      << ackermann(m,n) << std::endl;

   return 0;
}

---

My suggestions in a bulleted form:

• Follow the DRY principle. If you find yourself repeating code, there is most likely a way to remove repetition by defining a function and using the function in multiple places.

• Keep functions free of magic numbers as much as possible. In your case, the magic numbers 3 and 12 were moved to the calling function.

• Give names to what you are doing (isValidInput) and move them to their own functions.

• Keep functions as atomic as possible (separation of checking whether the input is valid and printing an error message).

• Make functions as generic as possible (converting getRawInput to a function template).

Answer 3

One way to improve is to use a database of lookup values to avoid repeated function calls. For example if your function calls ackermann(1,1) many times, retrieving from a database will prevent your program from naïvely opening unnecessary stack frames.

(Note: I don’t know C++ so my answer is in JavaScript.)

/** Database: a two-dimensional array of numbers */
const db = []

/** Set a value to an entry in the database. */
db.set = function (m, n, value) {
    // keep the row or add one if missing
    this[m] = this[m] || []
    // set the cell
    this[m][n] = value
}

/** Retrieve a value from the database. */
db.get = function (m, n) {
    // if row is an array and cell is a number, return that; else throw error
    if (this[m] instanceof Array && typeof this[m][n] === 'number') {
        return this[m][n]
    }
    throw new ReferenceError('No entry found.')
}

/** The Ackermann Function */
function ack(m, n) {
    // parameter validation:
    // if negative numbers, NaN, or infinite numbers are given, throw error
    if (m < 0 || n < 0 || Number.isNaN(m + n) || !Number.isFinite(m + n)) {
        throw new RangeError('Only natural numbers allowed.')
    }
    /** The returned result (the answer) */
    let returned;
    try {
        // try to get a database entry, if it exists
        returned = db.get(m, n)
    } catch (err) {
        // else, do Ackermann’s algorithm
        if (m === 0) {
            returned = n + 1
        } else if (n === 0) {
            returned = ack(m - 1, 1)
        } else {
            returned = ack(m - 1, ack(m, n - 1))
        }
        // make a new database entry for the result
        db.set(m, n, returned)
    }
    return returned
}