CSCI 265: Final Exam 1

Question 1: Debugging [9]

The function choose shown below is meant to calculate m choose n for integers m > 0 and n > 0.
The definition of m choose n is shown to the right.

Function implementation

Definition

long choose(long m, long n)
{
   return ((m < 1) || (n < 1)) ? 0 :
   ({ n = ((m - n) < n) ? m - n: n;
    long s = 1; for (int i = 0; i <= n;
    s *= (m+1-++i), s /= i);
    s;});
}

	m!

n!	(m-n)!

The function has been optimized to cancel out terms in the numerator and denonimator of the formula above, but not entirely correctly. As a result, it often (but not always) computes an incorrect value.

Problem:
You are to give a detailed description of how you would start debugging to identify the exact cause of the miscalculation, so that you could then correct the implementation. Your answer should precisely describe each of the following:

the (C++ driver) code you would write to call/test the function,
any temporary modifications you would make to the function itself to observe what it was doing,
the test values you would initially use for testing, and
the precise set of gdb commands you would use to observe what was taking place during the sequence of computations within the function.