questions about combination using recursion

[Larry Niven]

As we know, c(n, k) = c(n-1, k) + c(n-1, k-1).

Also, c(n, 0) = c(n, n) = 1

Therefore, I write down the following function.

int c(int n, int k){
if(n == k || k == 0){
return 1;
}else{
return c(n-1, k) + c(n-1, k-1);
}
}

However, the size of the return value is limited.

If 0 <= n, k <= 1000, the maximum will be c(1000, 500).

Even unsigned long is not enough for c(1000, 500).

How can I improve it?

 

[Sheldon Simms]

On Wed, 29 Oct 2003 04:54:40 -0800, Larry Niven wrote:

Nice to meet you Larry. Good to see you're programming
these days...

Even unsigned long is not enough for c(1000, 500).
How can I improve it?

unsigned long long may get you a bigger integer type. After
that you have to use a "bignum" library. One such library is:

http://www.swox.com/gmp/

-Sheldon

 

[Larry Niven]

unsigned long long may get you a bigger integer type. After
that you have to use a "bignum" library. One such library is:

http://www.swox.com/gmp/

-Sheldon

Thanks for your suggestion.

If I turn to BigNum, the function will become

BigNum * c(int n, int k){
if(n == k || k == 0){
/* Let BigNum = 1 */
return BigNum;
}else{
return BigNumAdd(c(n-1, k) + c(n-1, k-1));
/* The prototype of the function BigNumAdd will be
* BigNum * BigNumAdd(BigNum *a, BigNum *b) */
}
}

If I want to write my own BigNum for this particular program, which
will make this program small and clear for my other classmates to
discuss, then the BigNum stucture and the function BigNumAdd are the
only two things I need to worry about.

So, can someone tell me how to implement those?