Dave, Yep sorry, i over looked the implementation, its better than mine for a all numbers less than n :). I hope it don't happen again.
On Sun, Oct 10, 2010 at 12:38 AM, Dave <[email protected]> wrote: > @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 <[email protected]> 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 <[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]> > <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 [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.
