473,219 Members | 1,838 Online

# questions about combination using recursion

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?
Nov 13 '05 #1
2 4817
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

Nov 13 '05 #2
Sheldon Simms <sh**********@yahoo.com> wrote in message news:<pa****************************@yahoo.com>...

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

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?
Nov 13 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.