Just change it to
int CatalanNumber[1001];
int i,n;
long long int x;
CatalanNumber[0] = 1;
*CatalanNumber[1]=1;
for( n = 2 *; 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;
}
Or u l have seg fault :)
On Sun, Oct 10, 2010 at 12:53 AM, GUNJAN BANSAL
<gunjanbansal...@gmail.com>wrote:
> 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 <dave_and_da...@juno.com> 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 <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>
>> <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<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
>
>
--
*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 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.
