Answer to Q3 of HW1 and HW2:

To find the largest value of n such that we can calculate all the combinations of n, we should first devise an algorithm which avoids over- and underflow.

First of all, what causes an over-, and an underflow? If we try to find the combination using an algorithm that first tries to find n!, we are limited by this value. If it is larger than 10¹⁵ we can’t find the solution due to overflow. So why not divide by the denominator first? But this time we are not sure if 1/k! causes an underflow. Yet the smallest number is 10^-16 and this shows that we are freer in this region, i.e. an underflow is harder to achieve. So even this is a better solution than finding n! right away and note that there is no implication in HW1 that opposes this method. But this is not the best solution.

Here is one of the solutions to this problem:

First simplify the nominator and denominator to get rid of the (n-k)! factor in the denominator. Then put the remaining numbers in the nominator and denominator in two separate arrays nom[] and denom[]. Now consider the following pseudo code:

Comb = 1;

While denom[] has unused numbers {

If Comb > 1

Comb /= denom[nextdenom];

nextdenom++;

else

Comb *= nom[nextnom];

Nextnom++;

}

multiply Comb with remaining numbers on nom[];

Using this method we ensure that when the loop ends we are as close as possible to 1. All remaining numbers have to be in nom[], since its numbers are greater in value and more effective. So, if the remaining numbers cause an overflow, we can’t express the combination.

This way we are restricted to the largest value of the combination (n k), which is (n n/2) (remember the Pascal triangle). So the answer for this system is 53, not 17, which you can check for yourselves. The very big difference b/w 53 and 17 is a good example of the importance of numerical analysis.