471,601 Members | 1,725 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,601 software developers and data experts.

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 4755
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 leo001 | last post: by
reply views Thread by CCCYYYY | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.