Hi, The implementation that you are trying to do is incorrect, this is primarly because division is not commutative over modulous. You can check that with simple examples. eg 111 is divisible by 3, but taking modulus with 100 we get 11 which is not divisible by 3.
Catalan number is of the form Cn=(2(2n-1)/n+1)Cn-1 , here n+1 in division is creating problem. Better do this for any catalan number. Expand 2n! , n! , n+1! , depending on wiether n is even or n is odd u l get equation of the form (2^[n/2] * (n+3) (n+5) (n+7)..........(2n-1)) / [n/2]! were n/2 is lower and upper bound, check with a example. Calculate prime numbers, and sum the powers for numerator and subtract powers for denominrator. After that u can easily compute the modulous also. On Sat, Oct 9, 2010 at 9:04 PM, Dave <[email protected]> wrote: > There is a recurrence for computing the n+1st Catalan Number from the > 0th through the nth Catalan Numbers. See > http://en.wikipedia.org/wiki/Catalan_number. > > Something like this code fragment ought to do, assuming long long int > is 64 bits: > > int CatalanNumber[1001]; > int i,n; > long long int x; > CatalanNumber[0] = 1; > for( n = 0 ; n < 1000 ; ++n ) > { > x = 0; > for( i = 0 ; i <= n ; ++i ) > x += (long long int)CatalanNumber[i] * (long long > int)CatalanNumber[n-i]; > CatalanNumber[n+1] = x % 10000; > } > > Dave > > On Oct 9, 8:36 am, keyankarthi <[email protected]> wrote: > > can anyone suggest how to implement Catalan numbers.. upper limit > > 1000, > > > > consider modulo 10000 > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- *GUNjan BANsal* Programming is an art of organizing complexity - Dijkstra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
