Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #127076
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Catching overflow |
| Date | 2018-02-26 15:21 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <87r2p7sro9.fsf@bsb.me.uk> (permalink) |
| References | <p6vf4p$ot1$1@dont-email.me> <87efl8two2.fsf@bsb.me.uk> <p6vl8r$2c3$1@dont-email.me> <878tbgtudk.fsf@bsb.me.uk> <p70lfc$ia3$1@dont-email.me> |
jacobnavia <jacob@jacob.remcomp.fr> writes:
> Le 26/02/2018 à 02:25, Ben Bacarisse a écrit :
>
>>
>> Doing some of the calculation in 128 bits may be a needless
>> optimisation. With a series that grows this fast, a table is almost
>> always going to be the best way to go. A table of just 70 numbers can
>> hold all the 128-bit Catalan numbers. Even if you don't pre-compute
>> any, just caching these as they get computed would probably mean you can
>> use qfloats from the start.
>>
>
> You can compute up to catalan(62) in 128 bits without overflow. The
> computation of catalan(63) upwards needs more than 128 bits precision.
You can compute up to catalan(69) in 128 bits without overflow.
> I have already optimized that, without a table but just computing all
> catalan numbers less than 63 in 128 bits, what goes very fast.
Yup, speed is not a problem for small values.
> The problem is, for catalan numbers higher than 62, I can't cache the
> results since the goal number is involved in the computation from the
> start, and catalan(63) will have a VERY different value at iteration
> 62 than catalan(62)...
I don't follow this but then I don't know what algorithm you are using.
> But I can start computing a given catalan number in 128 bits and
> switch to 480 when the computation overflows.
>
> I am using this:
>
> https://www.geeksforgeeks.org/program-nth-catalan-number/
There's lots of algorithms there. I don't know which one you are using.
> I "ported" that to 128 bits, then to 480. I use this as a way of
> testing my extended precision floats in the ARM 64 environment.
I'm not sure what that format is, but even if it has 480 mantissa bits
you can only go up to catalan(246) so I would still use a table and a
naive algorithm like:
vtype catalan(int n)
{
static vtype cat_table[N_CAT];
if (n < 2) return 1;
if (n < N_CAT && cat_table[n]) return cat_table[n];
vtype c = 0;
for (int i = 0; i < n; i++)
c += catalan(i) * catalan(n-i-1);
return n < N_CAT ? cat_table[n] = c : c;
}
--
Ben.
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