468,532 Members | 1,716 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,532 developers. It's quick & easy.

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


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

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by pembed2003 | last post: by
13 posts views Thread by Raman | last post: by
3 posts views Thread by greek | last post: by
2 posts views Thread by wagn31 | last post: by
reply views Thread by NPC403 | last post: by
1 post views Thread by fmendoza | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.