Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #127147
| From | Ike Naar <ike@iceland.freeshell.org> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: Catching overflow |
| Date | 2018-02-27 20:14 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <slrn3s3op9bf06.moh.ike@iceland.freeshell.org> (permalink) |
| References | (3 earlier) <878tbgtudk.fsf@bsb.me.uk> <p70lfc$ia3$1@dont-email.me> <87r2p7sro9.fsf@bsb.me.uk> <p71gje$o1v$1@dont-email.me> <slrn3u84p9bd3g.sje.ike@iceland.freeshell.org> |
On 2018-02-27, Ike Naar <ike@iceland.freeshell.org> wrote:
> On 2018-02-26, jacobnavia <jacob@jacob.remcomp.fr> wrote:
>> 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;
>> }
>
> The first iteration can be eliminated (it always computes 1 * n / 1):
>
> unsigned __int128 binomialCoeff(unsigned __int128 n,unsigned __int128 k)
> {
> unsigned __int128 res = n;
>
> if (k > n - k)
> k = n - k;
>
> for (int i = 1; i < k; ++i)
> {
> res *= (n - i) / (i + 1);
> }
>
> return res;
> }
Please disregard this post, it doesn't work for k=0; sorry for the noise.
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