Re: Catching overflow

From	David Brown <david.brown@hesbynett.no>
Newsgroups	comp.lang.c
Subject	Re: Catching overflow
Date	2018-03-04 13:48 +0100
Organization	A noiseless patient Spider
Message-ID	<p7gpvl$ums$1@dont-email.me> (permalink)
References	(6 earlier) <p71gje$o1v$1@dont-email.me> <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>

Show all headers | View raw

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.

In any discussion of algorithmic complexity, it is also important to 
remember that the big O notation is only a measure of long-term 
efficiency as the values get bigger.  And to be done properly, you need 
to take into account the O complexity of the calculations.  For more 
useful efficiency analysis of practical sizes, you need to look at the 
actual complexity factors rather than just their tendency for very large 
sizes.

The additions needed for Pascal's Triangle are very efficient, and on 
modern cpus can be done with vector processing (to some extent at 
least).  They would also, I think, be suitable for graphics card 
acceleration, and will be cache-friendly as you only need to handle one 
row at a time.  As the numbers get bigger than you can reasonably handle 
in a 64-bit cpu, additions scale linearly with magnitude.

Multiplications, on the other hand, scale worse with magnitude.  You can 
do some SIMD acceleration, but not as much as with addition.  And 
divisions scale very badly with magnitude, cannot be done in SIMD or 
graphics cards, and typically lead to pipeline stalls and are often 
limited to a single non-pipelined execution unit taking many cycles.  In 
any speed-critical calculation, divisions are always something to avoid.

In short, Tim is correct for a single Binomial calculation, and from a 
theoretical viewpoint.  But it may be a very different matter in 
practice for the problem the OP wanted to solve, and is not nearly as 
simple as O(n) vs. O(n^2).

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