Essentially what I have tried to do in the above code is to calculate
1=C(n-r,0) => C(n-r+1,1) => C(n-r+2,2) ... => C(n-r + r,r)=C(n,r)
by using the iterative formula
C(n+1,r+1)=( (n+1)*C(n,r))/(r+1)
Printable View
Essentially what I have tried to do in the above code is to calculate
1=C(n-r,0) => C(n-r+1,1) => C(n-r+2,2) ... => C(n-r + r,r)=C(n,r)
by using the iterative formula
C(n+1,r+1)=( (n+1)*C(n,r))/(r+1)
I tried it pinko but it does not work. I found my mistake in the code. I should use double as a data type not int.
For what input?Quote:
Originally Posted by clover
It works for me fine.
Give me an n and a r for which it does not work.
My output for n=30
choose1(30,0)=1
choose1(30,1)=30
choose1(30,2)=435
choose1(30,3)=4060
choose1(30,4)=27405
choose1(30,5)=142506
choose1(30,6)=593775
choose1(30,7)=2035800
choose1(30,8)=5852925
choose1(30,9)=14307150
choose1(30,10)=30045015
choose1(30,11)=54627300
choose1(30,12)=86493225
choose1(30,13)=119759850
choose1(30,14)=145422675
choose1(30,15)=155117520
choose1(30,16)=145422675
choose1(30,17)=119759850
choose1(30,18)=86493225
choose1(30,19)=54627300
choose1(30,20)=30045015
choose1(30,21)=14307150
choose1(30,22)=5852925
choose1(30,23)=2035800
choose1(30,24)=593775
choose1(30,25)=142506
choose1(30,26)=27405
choose1(30,27)=4060
choose1(30,28)=435
choose1(30,29)=30
choose1(30,30)=1
Show me your code.Quote:
Originally Posted by clover
for n=14 r=11
31 C 15 : For function choose1() results were 14209041 correct value is 300540195. The values from that depth on breaks down. Same results for function choose().
I am getting 364 which is the correct answer.Quote:
Originally Posted by clover
That is an over flow, error, 31 is hitting the bar using this method.Quote:
Originally Posted by Thantos
Still if you want to push the bar further accumulate products in higher precision.
choose1(31,15) is 300540195 as you want.Code:#include <stdio.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++)
{
comb = ( (num+1)*comb )/(den+1);
}
return comb;
}
int
main(void)
{
unsigned long n,i;
printf("Give n\n");
scanf("%lu",&n);
printf("n=%lu\n",n);
for(i=0;i<=n;i++)
{
printf("choose1(%lu,%lu)=%llu\n",n,i,choose1(n,i));
}
return 0;
}
But you will of course find sufficiently large values of n for which this will break.
I corrected the code above a bit
The above code will work for C(n,r) iff
n*C(n-1,r-1) < 2**32-1
[added later]
It should ULLONG_MAX above, or 2**64-1
And that is why I choose to use the reduction method instead. Slower yes, more memory yes, larger range of accurate numbers yes. :)
Thantos,
What is the smallest value of C(2n,n) for which your method fails?
It fails at n 35 r 15 is the first failing point. n 36 r 18 is the 2n, n failing point.
Using the long long int format the 2n,n failing point appears to be 70,35
For my code its (64,32) so you are squeezing five more bionomial sequences.Quote:
Originally Posted by Thantos
Not bad!!! Good work!!!
Dude, what is the sizeof(unsigned long long) on your system,Quote:
Originally Posted by Thantos
C(70,35)= 112186277816662845432
ULLONG_MAX= 18446744073709551615 (on my system) :confused:
C(70,35) > ULLONG_MAX :confused: