@Gunjan: If you were referring to my implementation (it is the only one that I see), you'll notice that I used a different recurrence, the second formulation in the properties section of the Wikipedia page I referenced, that starts with C_0 = 1. It only uses multiplication, and multiplication and modulus do commute.
Dave On Oct 9, 1:34 pm, GUNJAN BANSAL <gunjanbansal...@gmail.com> wrote: > 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 <dave_and_da...@juno.com> 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 <keyankarthi1...@gmail.com> 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 algoge...@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > > . > > 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- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
