Ttykuu

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)

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
 << "nnCALCULATING..." << 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.

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) 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 

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.

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) 

/** 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) !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