Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #127626
| From | Ike Naar <ike@iceland.freeshell.org> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Catching overflow |
| Date | 2018-03-11 09:21 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <slrn3tlkpa9t87.e6p.ike@iceland.freeshell.org> (permalink) |
| References | (7 earlier) <slrn3fvop9942m.bjj.ike@iceland.freeshell.org> <kfn1sh7t1kx.fsf@x-alumni2.alumni.caltech.edu> <p734v1$kbq$1@dont-email.me> <kfnpo4lqx83.fsf@x-alumni2.alumni.caltech.edu> <p7gpvl$ums$1@dont-email.me> |
On 2018-03-04, David Brown <david.brown@hesbynett.no> wrote:
> On 03/03/18 11:17, Tim Rentsch wrote:
>> David Brown <david.brown@hesbynett.no> writes:
>>
>>> On 27/02/18 06:59, Tim Rentsch wrote:
>>>
>>>> Ike Naar <ike@iceland.freeshell.org> writes:
>>>>
>>>>> On 2018-02-26, jacobnavia <jacob@jacob.remcomp.fr> wrote:
>>>>>
>>>>>> // Returns value of Binomial Coefficient C(n, k)
>>>>>> unsigned __int128 binomialCoeff(unsigned __int128 n,unsigned __int128 k)
>>>>>> {
>>>>>> unsigned __int128 res = 1;
>>>>>>
>>>>>> // Since C(n, k) = C(n, n-k)
>>>>>> if (k > n - k)
>>>>>> k = n - k;
>>>>>>
>>>>>> // Calculate value of [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1]
>>>>>> for (int i = 0; i < k; ++i)
>>>>>> {
>>>>>> res *= (n - i);// <<<<<<< overflow will happen here
>>>>>> res /= (i + 1);
>>>>>> }
>>>>>>
>>>>>> return res;
>>>>>> }
>>>>>
>>>>> Binomial coefficients can be computed without multiplications
>>>>> or divisions (only additions), using Pascal's triangle.
>>>>
>>>> The algorithm shown runs in O( n ) time. An algorithm based
>>>> on Pascal's triangle runs in O( n**2 ) time.
>>>
>>> If you store the results as you go along, because you are using many
>>> values and not just one (the OP wants to generate a list of all Catalan
>>> numbers up to a point, not just individual numbers), then the time
>>> complexity is the same.
>>
>> Lest anyone be confused, this claim is wrong. Computing the
>> binomial coefficient C(2n,n) using Pascal's Triangle entails
>> calculating a number of distinct values that is proportional
>> to n**2, and so cannot be made to run faster than O( n**2 ).
>>
>
> Lest anyone be confused, this is missing the point.
>
> If you want to calculate a /single/ binomial coefficient, it can be done
> in O(n) time using a multiplication algorithm, or O(n^2) using summing
> of the Pascal's Triangle values.
>
> But if you want to calculate /lots/ of binomial coefficients - as you do
> for the OP's problem, where he wants to calculate a list of Catalan
> numbers - then it is a different matter. What is of interest there is
> the total calculations for all the binomial coefficients of interest,
> not just for /one/ coefficient. I have not looked at the details of how
> many binomial coefficients are needed to for generating a list of
> Catalan numbers, but if the density of required binomial coefficients is
> high enough, using Pascal's Triangle will be more efficient than
> calculating them individually with an O(n) algorithm.
Right. Just for fun, here's a toy program that computes n Catalan
numbers in O(2^n) time, using Pascal's triangle.
#include <stdio.h>
int main(void)
{
enum {N = 36};
unsigned long long b[2*N+1] = {1}; /* n'th row of Pascal's triangle */
for (size_t n = 0; n != N; ++n)
{
b[2*n+1] = 1;
for (size_t k = 2*n; k; --k) b[k] += b[k-1];
b[2*n+2] = 1;
for (size_t k = 2*n+1; k; --k) b[k] += b[k-1];
printf("catalan(%zu) = %llu\n", n+1, b[n+1] - b[n+2]);
}
return 0;
}
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-25 23:59 +0100
Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-02-26 00:32 +0100
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 01:45 +0100
Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 00:35 +0000
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 01:44 +0100
Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 01:25 +0000
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 10:53 +0100
Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 15:21 +0000
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:36 +0100
Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-26 22:55 +0000
Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-02-26 21:59 -0800
Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-02-27 09:30 +0100
Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-03 02:17 -0800
Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-03 03:19 -0800
Re: Catching overflow asetofsymbols@gmail.com - 2018-03-03 03:20 -0800
Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-03 03:50 -0800
Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-03-04 13:48 +0100
Re: Catching overflow asetofsymbols@gmail.com - 2018-03-04 07:11 -0800
Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-03-11 09:21 +0000
Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-03-11 09:26 +0000
Re: Catching overflow Tim Rentsch <txr@alumni.caltech.edu> - 2018-03-26 22:36 -0700
Re: Catching overflow David Brown <david.brown@hesbynett.no> - 2018-03-27 15:15 +0200
Re: Catching overflow Steven Petruzzellis <frelwizzen@gmail.com> - 2018-03-27 06:26 -0700
Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-27 19:41 +0000
Re: Catching overflow Ike Naar <ike@iceland.freeshell.org> - 2018-02-27 20:14 +0000
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-27 22:03 +0100
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:40 +0100
Re: Catching overflow Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-26 18:31 +0000
Re: Catching overflow Steve Carroll <frelwizzen@gmail.com> - 2018-03-01 08:45 -0800
Re: Catching overflow bartc <bc@freeuk.com> - 2018-02-26 01:12 +0000
Re: Catching overflow Richard Damon <Richard@Damon-Family.org> - 2018-02-25 23:10 -0500
Catching overflow asetofsymbols@gmail.com - 2018-02-25 22:09 -0800
Catching overflow asetofsymbols@gmail.com - 2018-02-25 23:30 -0800
Catching overflow asetofsymbols@gmail.com - 2018-02-25 23:31 -0800
Catching overflow asetofsymbols@gmail.com - 2018-02-28 00:03 -0800
Catching overflow asetofsymbols@gmail.com - 2018-02-28 22:49 -0800
Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-26 23:37 +0800
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 18:33 +0100
Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-28 22:31 +0800
Re: Catching overflow "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2018-02-28 22:33 +0800
Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 02:31 -0800
Re: Catching overflow asetofsymbols@gmail.com - 2018-03-01 05:45 -0800
Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 08:24 -0800
Re: Catching overflow asetofsymbols@gmail.com - 2018-03-01 09:03 -0800
Re: Catching overflow Steve Carroll <frelwizzen@gmail.com> - 2018-03-01 09:32 -0800
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 19:47 +0100
Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 10:58 -0800
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 20:08 +0100
Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 11:14 -0800
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-03-01 20:50 +0100
Re: Catching overflow already5chosen@yahoo.com - 2018-03-01 12:18 -0800
Re: Catching overflow supercat@casperkitty.com - 2018-03-03 15:08 -0800
Re: Catching overflow jladasky@itu.edu - 2018-02-26 13:07 -0800
Re: Catching overflow jacobnavia <jacob@jacob.remcomp.fr> - 2018-02-26 22:44 +0100
csiph-web