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;
}
