Thread: computing the number of combinations

1. long long is 64 on mine.

From my limits.h file:
# define ULLONG_MAX 18446744073709551615ULL
Hmm just realized that you can have a space(s) between the # and the macro type.

Yes C(70,35) is outside of the range, which is why I said it failed at that point.

2. Originally Posted by Thantos
long long is 64 on mine.

From my limits.h file:

Hmm just realized that you can have a space(s) between the # and the macro type.

Yes C(70,35) is outside of the range, which is why I said it failed at that point.
Even C(68,34)=28453041475240576740
is greater than 18446744073709551615 = ULLONG_MAX
by a factor of 1.5

The largest C(2n,n) that fits into a unsigned long long is C(66,33)
Assuming usigned long long is 64 bits wide.

The code below hopefully should calculate C(n,r) whenever the answer fits in unsigned long long, the reason for that it calculates C(n,r) by combing values which are less than C(n,r). If overflow occurs it should exit giving an error message.

It gives the correct value for C(67,33)=14226520737620288370.
The final value it can calculate is C(68,30)=17876288714431443296
Note, that C(68,31)=21912870037044995008 is
greater than 18446744073709551615 =ULLONG_MAX
So, I guess, the following program calculates C(n,r) whenever answer fits in unsigned long long and gives an error otherwise.

Code:
```#include <stdio.h>
#include <limits.h>
#include <stdlib.h>

unsigned long long
choose1(unsigned long n, unsigned long r) /*non recursive version*/
{
unsigned long long comb=1,num,den;
if( 2*r>n) r=n-r;
if( (r<0) || (r>n) ) return 0;/*error*/
for(num=n-r,den=0;num<n;num++,den++)
{
unsigned long long q=comb/(den+1);
unsigned long long r=comb-q*(den+1);
if (   ( ULLONG_MAX/(num+1) < q) ||
(ULLONG_MAX-((r*(num+1))/(den+1)) < (num+1)*q          )
)
{
fprintf(stderr,"Overflow detected...exiting\n");
exit(EXIT_FAILURE);
}
comb = (num+1)*q+((r*(num+1))/(den+1));
}
return comb;
}

int
main(void)
{
unsigned long n,r;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
printf("Give r\n");
scanf("%lu",&r);
printf("C(%lu,%lu)=%llu\n",n,r,choose1(n,r));
return 0;
}```

3. To explain what I have done is
I calculate C(n+1,r+1) from C(n,r) using the formula

C(n+1,r+1)= (n+1)*C(n,r)/(r+1)

I break up C(n,r)=q(r+1)+rem
where

0<=rem<=r

So, the above product can be written as the sum of two smaller quatities

(n+1)*q+ ( (n+1)*rem/(r+1))

the second term is less than n since rem < r+1 and note that the second term must be an integer

So, the overflow can only come from (n+1)*q exceeding ULLONG_MAX or the sum exceeding ULLONG_MAX in either case C(n+1,r+1) exceeds ULLONG_MAX.

4. What if i want to calculate C(200,100) without using special libraries. Any ideas?

5. >What if i want to calculate C(200,100) without using special libraries.
You'll have to duplicate the functionality of those special libraries manually.