Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #127049 > unrolled thread

Catching overflow

Back to article view | Back to comp.lang.c

Contents

  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

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#128414

David Brown <david.brown@hesbynett.no> writes:

> 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).

What I find remarkable about these comments is the combination of
a lecturing tone and a lack of understanding about the problem.

The earlier context for the problem is computing Catalan numbers
in a floating-point format (or integers for small values, but
that doesn't affect things significantly).  In floating-point,
all the basic operations run in O(1) time, so that isn't going to
change things much.  The standard floating-point types (double
and long double) run into exponent limits at about 500 and 8200,
respectively, so if we want to compute, say, the first 1,000,000
Catalan numbers (in floating-point) we need something more like
the 480-bit floating-point format that was mentioned upthread.
It's worth remembering that using Pascal's triangle takes O(n)
storage, whereas the iterative algorithm uses only O(1) storage.
For a million entries at 60 bytes/entry, that's 60 megabytes.
That much memory is likely to be a cache killer.

Okay, now suppose we want to compute exact Catalan numbers using
multiple-precision arithmetic.  For addition, we might be able to
take advantage of vector processing, or offloading to a GPU, but
again that is only a constant factor.  Multiplcation scales worse
than addition in the general case - O( n log n log log n ) versus
O(n) - but in this case the operations being performed (one
multiplication and one division) have single-word values for one
operand, which again makes them O(n), just like addition.  Because
the values are larger, we need O(n) space for the iterative
multiplying algorithm, but O(n*n) space for the Pascal's triangle
approach.  That's an enormous amount of memory if we try to use
Pascal's triangle to compute a million Catalan numbers.

And finally, the key point.  A simple iterative loop like the one
shown computes not just one Catalan number but all of the first N
Catalan numbers in O(N) operations.  The factor of N totally
kills the O(N*N) operations needed by the Pascal's triangle
approach.  A short program using multiplies and divides computes
exactly the first million Catalan numbers in a little under 11
minutes.  Anyone trying to do the same thing using Pascal's
triangle should be prepared for a very long wait.

By the way, the next time you're thinking of accusing someone of
missing the point, you might want to think two or three times
about whether it was you who missed it.

[toc] | [prev] | [next] | [standalone]

#128429

On 27/03/18 07:36, Tim Rentsch wrote:
> David Brown <david.brown@hesbynett.no> writes:
> 
>> 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).
> 
> What I find remarkable about these comments is the combination of
> a lecturing tone and a lack of understanding about the problem.

Feel free to re-read your own post - you will see who first used a
"lecturing tone".  I merely copied your phrasing.

> 
> The earlier context for the problem is computing Catalan numbers
> in a floating-point format (or integers for small values, but
> that doesn't affect things significantly).  In floating-point,
> all the basic operations run in O(1) time, so that isn't going to
> change things much.  The standard floating-point types (double
> and long double) run into exponent limits at about 500 and 8200,
> respectively, so if we want to compute, say, the first 1,000,000
> Catalan numbers (in floating-point) we need something more like
> the 480-bit floating-point format that was mentioned upthread.

This is true on a mythical machine with single-cycle 480-bit floating
point arithmetic.  In reality, as I said, the basic arithmetic
operations are not O(1) regardless of the size of the numbers, and with
the sizes we are talking about here (which are not /that/ big), the
scale factors are critical.

To give some examples, for an Intel i7 using 64-bit integer arithmetic
instructions and register-to-register operands, you can do 3 adds per
clock, but only one multiply, and a division takes up to 69 clocks.  For
each doubling of the bit width, you double the time for the addition
(and increase latency due to the dependency on the carry), scale by 3
for the multiply (until you get to very big numbers), and the division
immediately gets far slower and more complex (again, scaling is better
for massive numbers).  Floating point has much the same scaling rates as
integers here, as does SIMD operations.



> It's worth remembering that using Pascal's triangle takes O(n)
> storage, whereas the iterative algorithm uses only O(1) storage.
> For a million entries at 60 bytes/entry, that's 60 megabytes.
> That much memory is likely to be a cache killer.

That is definitely true, and an important consideration for practical
calculations.  However, you don't need to keep the whole triangle, you
only need to keep one row of it in memory at a time.  To calculate the
first N Catalan numbers, you only need 2*N+1 entries.  (See Ike's post
for the algorithm and code.)

I tested Ike's code against Jacob's code (which calculates the binomial
coefficient directly), using 128 bit integers and calculating up to 62
Catalan numbers (at which point Jacob's method overflowed, though Ike's
is good for another 5 numbers).  Calculating with Pascal's Triangle gave
a speed up factor of about 6 or 7.  This is fairly consistent for
different sizes of N, and with 64-bit integers (when N is 32 or less).

How well will these results scale?  I don't know for sure, but I expect
that as the sizes increase and the numbers get bigger, the Pascal's
triangle method will keep approximately the same factor.  To calculate
Catalan number n, when you already have row 2*n + 1 of Pascal's triangle
in the array, requires two runs through the array, doing 2*n additions
each time.  That is 4 * n simple calculations.  As your numbers get
bigger, the complexity of these calculations scales linearly with the
size of your integer type.

For the direct binomial calculation, calculating the coefficient
involves n multiplications and n divisions.  As the integer type gets
bigger, it is important to note that the multiplications and divisions
are of the form (big int) * (small int) and (big int) / (small int), and
thus the operations here also scale linearly with the size of the big
integer type.  (Without that optimisation, scaling gets worse.)

Eventually, with large enough numbers involved, you will reach a point
where cache effects for storing one line of Pascal's triangle become
relevant - and perhaps even counter the benefits of the simpler
operations.    But I think by that stage you would be wanting to look at
more advanced implementations anyway - using multiple threads, SIMD,
graphics cards, etc.

> 
> Okay, now suppose we want to compute exact Catalan numbers using
> multiple-precision arithmetic.  For addition, we might be able to
> take advantage of vector processing, or offloading to a GPU, but
> again that is only a constant factor.  Multiplcation scales worse
> than addition in the general case - O( n log n log log n ) 

That is hardly in "the general case" - that algorithm begins to make
sense for 10,000 digit numbers.  That would be Catalan number 1500 or
so, which is going /well/ beyond the OP's question.  But I agree that
this is the best known scaling for large integer multiplications.

> versus
> O(n) - but in this case the operations being performed (one
> multiplication and one division) have single-word values for one
> operand, which again makes them O(n), just like addition.  

Yes.

> Because
> the values are larger, we need O(n) space for the iterative
> multiplying algorithm, but O(n*n) space for the Pascal's triangle
> approach.

No.

We need O(n) space - only the last line of the triangle needs to be held.

>  That's an enormous amount of memory if we try to use
> Pascal's triangle to compute a million Catalan numbers.

For calculating a million Catalan numbers, we need approximately two
million bit numbers - 256KB per number.  Even one row of Pascal's
triangle is then 256 GB  at that size, which a bit over the top for
playing around on a PC.

But if you try to count out the operations needed, you'll see they are
unrealistically huge too - you have O(n) "big" operations
(multiplications, divisions), each of which takes O(n) "small"
operations (since they scale with the log of the numbers involved, and
the log of C(n) scales with n).  And remember we are generating a list
of Catalan numbers, not just C(1,000,000) - thus we have another O(n) to
add in.  So the operations scale at O(n^3) for both methods.

> 
> And finally, the key point.  A simple iterative loop like the one
> shown computes not just one Catalan number but all of the first N
> Catalan numbers in O(N) operations.  The factor of N totally
> kills the O(N*N) operations needed by the Pascal's triangle
> approach.  A short program using multiplies and divides computes
> exactly the first million Catalan numbers in a little under 11
> minutes.  Anyone trying to do the same thing using Pascal's
> triangle should be prepared for a very long wait.

I have realised the root of our disagreement.  You are not comparing the
algorithms in this part of the thread (Jakob's algorithm compared to
Ike's Pascal Triangle algorithm).  You have jumped back to Ben's
algorithm that got snipped earlier in the thread.  Now, I fully agree
that /that/ algorithm is far more efficient than either Jakob's or the
Pascal Triangle algorithm.  There are other recurrence relations that
could also be used to calculate Catalan numbers more efficiently - if
you can comprehend his post, asetofsymbols showed one.  But the point of
this branch was comparing the Pascal's triangle algorithm to Jacob's
algorithm.

> 
> By the way, the next time you're thinking of accusing someone of
> missing the point, you might want to think two or three times
> about whether it was you who missed it.
> 

Sound advice for me - but also for you.  We both missed each other's
point.  I believe if either one of us had looked more carefully at the
surrounding context of posts, we could both have realised that we were
talking somewhat at cross purposes.

Perhaps we should just call this an interesting exercise in algorithmic
complexity, and leave it there.

[toc] | [prev] | [next] | [standalone]

#128430

On Tuesday, March 27, 2018 at 6:15:38 AM UTC-7, David Brown wrote:
> On 27/03/18 07:36, Tim Rentsch wrote:
> > David Brown <david.brown@hesbynett.no> writes:
> > 
> >> 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).
> > 
> > What I find remarkable about these comments is the combination of
> > a lecturing tone and a lack of understanding about the problem.
> 
> Feel free to re-read your own post - you will see who first used a
> "lecturing tone".  I merely copied your phrasing.
> 
> > 
> > The earlier context for the problem is computing Catalan numbers
> > in a floating-point format (or integers for small values, but
> > that doesn't affect things significantly).  In floating-point,
> > all the basic operations run in O(1) time, so that isn't going to
> > change things much.  The standard floating-point types (double
> > and long double) run into exponent limits at about 500 and 8200,
> > respectively, so if we want to compute, say, the first 1,000,000
> > Catalan numbers (in floating-point) we need something more like
> > the 480-bit floating-point format that was mentioned upthread.
> 
> This is true on a mythical machine with single-cycle 480-bit floating
> point arithmetic.  In reality, as I said, the basic arithmetic
> operations are not O(1) regardless of the size of the numbers, and with
> the sizes we are talking about here (which are not /that/ big), the
> scale factors are critical.
> 
> To give some examples, for an Intel i7 using 64-bit integer arithmetic
> instructions and register-to-register operands, you can do 3 adds per
> clock, but only one multiply, and a division takes up to 69 clocks.  For
> each doubling of the bit width, you double the time for the addition
> (and increase latency due to the dependency on the carry), scale by 3
> for the multiply (until you get to very big numbers), and the division
> immediately gets far slower and more complex (again, scaling is better
> for massive numbers).  Floating point has much the same scaling rates as
> integers here, as does SIMD operations.
> 
> 
> 
> > It's worth remembering that using Pascal's triangle takes O(n)
> > storage, whereas the iterative algorithm uses only O(1) storage.
> > For a million entries at 60 bytes/entry, that's 60 megabytes.
> > That much memory is likely to be a cache killer.
> 
> That is definitely true, and an important consideration for practical
> calculations.  However, you don't need to keep the whole triangle, you
> only need to keep one row of it in memory at a time.  To calculate the
> first N Catalan numbers, you only need 2*N+1 entries.  (See Ike's post
> for the algorithm and code.)
> 
> I tested Ike's code against Jacob's code (which calculates the binomial
> coefficient directly), using 128 bit integers and calculating up to 62
> Catalan numbers (at which point Jacob's method overflowed, though Ike's
> is good for another 5 numbers).  Calculating with Pascal's Triangle gave
> a speed up factor of about 6 or 7.  This is fairly consistent for
> different sizes of N, and with 64-bit integers (when N is 32 or less).
> 
> How well will these results scale?  I don't know for sure, but I expect
> that as the sizes increase and the numbers get bigger, the Pascal's
> triangle method will keep approximately the same factor.  To calculate
> Catalan number n, when you already have row 2*n + 1 of Pascal's triangle
> in the array, requires two runs through the array, doing 2*n additions
> each time.  That is 4 * n simple calculations.  As your numbers get
> bigger, the complexity of these calculations scales linearly with the
> size of your integer type.
> 
> For the direct binomial calculation, calculating the coefficient
> involves n multiplications and n divisions.  As the integer type gets
> bigger, it is important to note that the multiplications and divisions
> are of the form (big int) * (small int) and (big int) / (small int), and
> thus the operations here also scale linearly with the size of the big
> integer type.  (Without that optimisation, scaling gets worse.)
> 
> Eventually, with large enough numbers involved, you will reach a point
> where cache effects for storing one line of Pascal's triangle become
> relevant - and perhaps even counter the benefits of the simpler
> operations.    But I think by that stage you would be wanting to look at
> more advanced implementations anyway - using multiple threads, SIMD,
> graphics cards, etc.
> 
> > 
> > Okay, now suppose we want to compute exact Catalan numbers using
> > multiple-precision arithmetic.  For addition, we might be able to
> > take advantage of vector processing, or offloading to a GPU, but
> > again that is only a constant factor.  Multiplcation scales worse
> > than addition in the general case - O( n log n log log n ) 
> 
> That is hardly in "the general case" - that algorithm begins to make
> sense for 10,000 digit numbers.  That would be Catalan number 1500 or
> so, which is going /well/ beyond the OP's question.  But I agree that
> this is the best known scaling for large integer multiplications.
> 
> > versus
> > O(n) - but in this case the operations being performed (one
> > multiplication and one division) have single-word values for one
> > operand, which again makes them O(n), just like addition.  
> 
> Yes.
> 
> > Because
> > the values are larger, we need O(n) space for the iterative
> > multiplying algorithm, but O(n*n) space for the Pascal's triangle
> > approach.
> 
> No.
> 
> We need O(n) space - only the last line of the triangle needs to be held.
> 
> >  That's an enormous amount of memory if we try to use
> > Pascal's triangle to compute a million Catalan numbers.
> 
> For calculating a million Catalan numbers, we need approximately two
> million bit numbers - 256KB per number.  Even one row of Pascal's
> triangle is then 256 GB  at that size, which a bit over the top for
> playing around on a PC.
> 
> But if you try to count out the operations needed, you'll see they are
> unrealistically huge too - you have O(n) "big" operations
> (multiplications, divisions), each of which takes O(n) "small"
> operations (since they scale with the log of the numbers involved, and
> the log of C(n) scales with n).  And remember we are generating a list
> of Catalan numbers, not just C(1,000,000) - thus we have another O(n) to
> add in.  So the operations scale at O(n^3) for both methods.
> 
> > 
> > And finally, the key point.  A simple iterative loop like the one
> > shown computes not just one Catalan number but all of the first N
> > Catalan numbers in O(N) operations.  The factor of N totally
> > kills the O(N*N) operations needed by the Pascal's triangle
> > approach.  A short program using multiplies and divides computes
> > exactly the first million Catalan numbers in a little under 11
> > minutes.  Anyone trying to do the same thing using Pascal's
> > triangle should be prepared for a very long wait.
> 
> I have realised the root of our disagreement.  You are not comparing the
> algorithms in this part of the thread (Jakob's algorithm compared to
> Ike's Pascal Triangle algorithm).  You have jumped back to Ben's
> algorithm that got snipped earlier in the thread.  Now, I fully agree
> that /that/ algorithm is far more efficient than either Jakob's or the
> Pascal Triangle algorithm.  There are other recurrence relations that
> could also be used to calculate Catalan numbers more efficiently - if
> you can comprehend his post, asetofsymbols showed one.  But the point of
> this branch was comparing the Pascal's triangle algorithm to Jacob's
> algorithm.
> 
> > 
> > By the way, the next time you're thinking of accusing someone of
> > missing the point, you might want to think two or three times
> > about whether it was you who missed it.
> > 
> 
> Sound advice for me - but also for you.  We both missed each other's
> point.  I believe if either one of us had looked more carefully at the
> surrounding context of posts, we could both have realised that we were
> talking somewhat at cross purposes.
> 
> Perhaps we should just call this an interesting exercise in algorithmic
> complexity, and leave it there.



On topic discussions will be overwhelmed once the waters are overfished. That, and there will always be a snit thrower or more in an unmoderated group (i.e. Autumn Nissen (https://www.facebook.com/anissen7)). The comedy of errors aside, we have all seen who usually gets enraged when he does not get anyone to shill for him. It is clear from the way Autumn Nissen (https://www.facebook.com/anissen7) posted - by showing ignorance of details of the system and the like - he has not figured out a computationally complex issue before. Otherwise he would have understood the requirements including being POSIX compliant! Just moronic trolling. And I am replying to that trolling. THAT is what the "Autumn Nissen (https://www.facebook.com/anissen7) circus" is. How long has this debate been going on? Audra Moore can create a virtual machine. Make sure to send him a gold star! My view is much more sophisticated. 

--
Eight things to never feed your dog!
https://youtu.be/qwb1Ez0GWMA
http://www.5z8.info/gruesome-gunshot-wounds_t5z0au_cockdock.gif
Jonas Eklundh

[toc] | [prev] | [next] | [standalone]

#127144

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;
  }

[toc] | [prev] | [next] | [standalone]

#127147

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.

[toc] | [prev] | [next] | [standalone]

#127148

Le 27/02/2018 à 21:14, Ike Naar a écrit :
> Please disregard this post, it doesn't work for k=0; sorry for the noise.

I know, I did the same mistake Ike

:-)

[toc] | [prev] | [next] | [standalone]

#127086

Le 26/02/2018 à 16:21, Ben Bacarisse a écrit :
> I'm not sure what that format is, but even if it has 480 mantissa bits
> you can only go up to catalan(246)

No, because itr is a 480 bits FLOATING POINT format, so I have a maximum 
exponent of pow(10,1048576) !!!


* catalan(2000)
8.31033420806514277630952936761809874071077260064288028 \
5497172797668390892100214567591803395202640482817294746 \
21481841400922937726151E+1198

Of course I get "only" the first 135 digits...

[toc] | [prev] | [next] | [standalone]

#127089

jacobnavia <jacob@jacob.remcomp.fr> writes:

> Le 26/02/2018 à 16:21, Ben Bacarisse a écrit :
>> I'm not sure what that format is, but even if it has 480 mantissa bits
>> you can only go up to catalan(246)
>
> No, because itr is a 480 bits FLOATING POINT format, so I have a
> maximum exponent of pow(10,1048576) !!!
>
> * catalan(2000)
> 8.31033420806514277630952936761809874071077260064288028 \
> 5497172797668390892100214567591803395202640482817294746 \
> 21481841400922937726151E+1198
>
> Of course I get "only" the first 135 digits...

There abouts.  You seem to have about 131 or 132 digits.

I was assuming you were calculating the Catalan numbers using floating
point.  In fact you are using floating point to approximate Catalan
numbers.  That's fine, by the way, I'm just explaining why we were not
understanding each other.  I'm now no longer sure why you want to do
part of this in 128-bit integers but that's probably just down to me not
knowing what you are trying to achieve.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#127177

On Sunday, February 25, 2018 at 5:44:24 PM UTC-7, jacobnavia wrote:
> Le 26/02/2018 à 01:35, Ben Bacarisse a écrit :
> > jacobnavia <jacob@jacob.remcomp.fr> writes:
> > 
> >> I want to do the computation of catalan numbers in 480 bits (my qfloat
> >> extension to C)
> > 
> > Are approximate values OK?  I'm not sure what role floating point is
> > going to play here.
> > 
> >> But I would like to do as much calculations in 128 bits only (at the
> >> start of the series) as possible.
> >>
> >> Possible means until before the computation overflows.
> >>
> >> How can I know if a multiplication will overflow in 128 bits?
> >>
> >> Let's see:
> >>
> >> I want to know when
> >>
> >> 	A x B > pow(2,128)
> >>
> >> (A and B < pow(2,64), unsigned long long data)
> > 
> > Is that a typo?  If A and B are both < pow(2,64), A*B will not be >
> > pow(2,128).
> > 
> > <snip>
> > 
> You arez right. I wanted to go a bit further, so I casted into 128 bits, 
> so A and B could be bigger than 2^64
> 
> Sorry about that



From what I've seen (which is none of it lately), it looks like the Systemd ecosystem needs more and more resources. 

When I was not seeking acceptance of the herd, I wanted to be equitable and unaffected by herd views. I gave bartc more than an intelligent person generally would. That lame duck update system failed over and over again. 

It was bartc who forged me (and others) and did not even try to hide it. 

This is something you should ask Paul F. Riddle. 

His hope is to see Paul F. Riddle irritated by nonstop flooding. And hey, that could kill this group. 

Do you have a high school diploma? 

-- 
Live on Kickstarter!
http://www.5z8.info/titstitstitstits_j7t4bl_stalin
Jonas Eklundh Communication AB

[toc] | [prev] | [next] | [standalone]

#127062

On 25/02/2018 22:59, jacobnavia wrote:
> I want to do the computation of catalan numbers in 480 bits (my qfloat 
> extension to C)
> 
> But I would like to do as much calculations in 128 bits only (at the 
> start of the series) as possible.
> 
> Possible means until before the computation overflows.
> 
> How can I know if a multiplication will overflow in 128 bits?
> 
> Let's see:
> 
> I want to know when
> 
>      A x B > pow(2,128)
> 
> (A and B < pow(2,64), unsigned long long data)

Do you mean pow(2,128) here too? Otherwise A*B will never overflow 128 bits.

> If I take logarithms (base 2)
> 
>      log(A) + log(B) > 128*log2
>      log(A) + log(B) > 88.7228
> 
> But log(A) using base 2 is just the rank of the first non-zero bit, for 
> instance:
> log(64) / log(2) --> 6, 64 has the sixth bit 1.
> 
> log(65) / log(2) --> 6.022, so floor(log(65)/log(2)) stil gives me the 
> first 1 bit: bit 6, since 65 is 1000001. And this holds until 127, since
> 
> log(127)/log(2) --> 6.988 127 is 1111111, the first 1 position doesn't 
> change.

I make it that if log2(A) + log2(B) >= 128, then overflow will 
definitely occur.

But if log2(A)+log2(B) is 127, then overflow might still occur.

Working on 8-bit values 0..255 to make things clearer, and using 12[3] 
to mean that value 12 has log2 value of 3 (the value you will get with 
BSR which ignores the fractional part) then:

   8[3]  x 32[5] = 256[8]    # the log2s add to 8 or more, so overflow
   8[3]  x 31[4] = 248[7]    # logs give 7, so no overflow in this case
   12[3] x 31[4] = 372[7]    # logs still give 7, but this overflows

So I'm not sure is summing these partial logs will give a definitive answer.

I /think/ (not being a mathematician) that logs2 adding to 8 or more: 
overflow; 6 or less: will not overflow; and 7: it might.

But with only 8 bits, you can evaluate all the combinations, and I did 
find that when log2(A)+log2(B) was 7 (ie. 127 for 128-bits), then 
sometimes it overflowed and sometimes it didn't.

-- 
bartc

[toc] | [prev] | [next] | [standalone]

#127065

On 2/25/18 8:12 PM, bartc wrote:
> On 25/02/2018 22:59, jacobnavia wrote:
>> I want to do the computation of catalan numbers in 480 bits (my qfloat 
>> extension to C)
>>
>> But I would like to do as much calculations in 128 bits only (at the 
>> start of the series) as possible.
>>
>> Possible means until before the computation overflows.
>>
>> How can I know if a multiplication will overflow in 128 bits?
>>
>> Let's see:
>>
>> I want to know when
>>
>>      A x B > pow(2,128)
>>
>> (A and B < pow(2,64), unsigned long long data)
> 
> Do you mean pow(2,128) here too? Otherwise A*B will never overflow 128 
> bits.
> 
>> If I take logarithms (base 2)
>>
>>      log(A) + log(B) > 128*log2
>>      log(A) + log(B) > 88.7228
>>
>> But log(A) using base 2 is just the rank of the first non-zero bit, 
>> for instance:
>> log(64) / log(2) --> 6, 64 has the sixth bit 1.
>>
>> log(65) / log(2) --> 6.022, so floor(log(65)/log(2)) stil gives me the 
>> first 1 bit: bit 6, since 65 is 1000001. And this holds until 127, since
>>
>> log(127)/log(2) --> 6.988 127 is 1111111, the first 1 position doesn't 
>> change.
> 
> I make it that if log2(A) + log2(B) >= 128, then overflow will 
> definitely occur.
> 
> But if log2(A)+log2(B) is 127, then overflow might still occur.
> 
> Working on 8-bit values 0..255 to make things clearer, and using 12[3] 
> to mean that value 12 has log2 value of 3 (the value you will get with 
> BSR which ignores the fractional part) then:
> 
>    8[3]  x 32[5] = 256[8]    # the log2s add to 8 or more, so overflow
>    8[3]  x 31[4] = 248[7]    # logs give 7, so no overflow in this case
>    12[3] x 31[4] = 372[7]    # logs still give 7, but this overflows
> 
> So I'm not sure is summing these partial logs will give a definitive 
> answer.
> 
> I /think/ (not being a mathematician) that logs2 adding to 8 or more: 
> overflow; 6 or less: will not overflow; and 7: it might.
> 
> But with only 8 bits, you can evaluate all the combinations, and I did 
> find that when log2(A)+log2(B) was 7 (ie. 127 for 128-bits), then 
> sometimes it overflowed and sometimes it didn't.
> 

The simple math is that if the floor of the log (what you get with BSR) 
is x, then the real log is x+1 > log(A) >= x.

this means that the log(A*B) will be at least floor(log(A)) + 
floor(log(B)) and will be less than floor(log(A)) + floor(log(B)) + 2

Thus you want the sum of the logs to be 2 less than the log of the first 
value that overflows.

[toc] | [prev] | [next] | [standalone]

#127066

 Catching overflow 











Feb 25  Jacob Navia  






I want to do the computation of catalan numbers in 480 bits (my qfloat 
extension to C) 

But I would like to do as much calculations in 128 bits only (at the 
start of the series) as possible. 

Possible means until before the computation overflows. 

How can I know if a multiplication will overflow in 128 bits? 

Let's see: 

I want to know when 

        A x B > pow(2,128) 

(A and B < pow(2,64), unsigned long long data) 

If I take logarithms (base 2) 

        log(A) + log(B) > 128*log2 
        log(A) + log(B) > 88.7228
---
If base of log is 2
log A + log B<=128
Because log 2 has to be 1
Than log A it should be "the length of A as array its bit" or something as that.
Perhaps it is better one type never overflow (if not memory end)
and doing A *B <2^128

[toc] | [prev] | [next] | [standalone]

#127068

If bsr find the position of the first most significative bit != 0

The code should be:

if(bsr(A)+bsr(B)>128) 
                break; // overflow 

[toc] | [prev] | [next] | [standalone]

#127069

It is >=128
Above

[toc] | [prev] | [next] | [standalone]

#127154

num catalan(num  n)
{num r;
 if(n==0u)R (num)1;
 r=catalan(n-1u);
 R ((4u*n-2u)*r)/(n+1u);
}

int main28(void)
{num i;
 F(i=0u;i<131u;++i)
    {ooo<<catalan(i)<<" ";
     if(i>20u)P("i=%u\n",i.numer.num[0]);
    }
 ooo<<"\n";
 R 0;   
}

int  main(void)
{int  r;
 if(InCppDLL()==0) R   0;
 *Alibero_m_=1;
 P("Alibero=%u\n", *Alibero_m_);
 *MostraStatistiche=1;
 r=main28(); // r=mainV()
 OutCppDLL();
 R  r;
}

This would be C++ code where P is one printflike function and ooo is a cout like function, R==Return F==for
this should not overflow until memory end

Main problem i found is num catalan(num&) return wrong results.
The system seems not have leaks at end (so C++ compiler it seems allocate and free right the num object return each function, the same for the num as argument of function Catalan)

For reference, the recursive implementation in page: 
https://codegolf.stackexchange.com/questions/66127/catalan-numbers

------------------
Alibero=1
1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 742900 2674440 9694845 35357670
 129644790 477638700 1767263190 6564120420 24466267020 i=21
91482563640 i=22
343059613650 i=23
1289904147324 i=24
4861946401452 i=25
18367353072152 i=26
69533550916004 i=27
263747951750360 i=28
1002242216651368 i=29
3814986502092304 i=30
14544636039226909 i=31
55534064877048198 i=32
212336130412243110 i=33
812944042149730764 i=34
3116285494907301262 i=35
11959798385860453492 i=36
45950804324621742364 i=37
176733862787006701400 i=38
680425371729975800390 i=39
2622127042276492108820 i=40
10113918591637898134020 i=41
39044429911904443959240 i=42
150853479205085351660700 i=43
583300119592996693088040 i=44
2257117854077248073253720 i=45
8740328711533173390046320 i=46
33868773757191046886429490 i=47
131327898242169365477991900 i=48
509552245179617138054608572 i=49
1978261657756160653623774456 i=50
7684785670514316385230816156 i=51
29869166945772625950142417512 i=52
116157871455782434250553845880 i=53
451959718027953471447609509424 i=54
1759414616608818870992479875972 i=55
6852456927844873497549658464312 i=56
26700952856774851904245220912664 i=57
104088460289122304033498318812080 i=58
405944995127576985730643443367112 i=59
1583850964596120042686772779038896 i=60
6182127958584855650487080847216336 i=61
24139737743045626825711458546273312 i=62
94295850558771979787935384946380125 i=63
368479169875816659479009042713546950 i=64
1440418573150919668872489894243865350 i=65
5632681584560312734993915705849145100 i=66
22033725021956517463358552614056949950 i=67
86218923998960285726185640663701108500 i=68
337485502510215975556783793455058624700 i=69
1321422108420282270489942177190229544600 i=70
5175569924646105559418940193995065716350 i=71
20276890389709399862928998568254641025700 i=72
79463489365077377841208237632349268884500 i=73
311496878311103321137536291518809134027240 i=74
1221395654430378811828760722007962130791020 i=75
4790408930363303911328386208394864461024520 i=76
18793142726809884575211361279087545193250040 i=77
73745243611532458459690151854647329239335600 i=78
289450081175264899454283846029490767264392230 i=79
1136359577947336271931632877004667456667613940 i=80
4462290049988320482463241297506133183499654740 i=81
17526585015616776834735140517915655636396234280 i=82
68854441132780194707888052034668647142985206100 i=83
270557451039395118028642463289168566420671280440 i=84
1063353702922273835973036658043476458723103404520 i=85
4180080073556524734514695828170907458428751314320 i=86
16435314834665426797069144960762886143367590394940 i=87
64633260585762914370496637486146181462681535261000 i=88
254224158304000796523953440778841647086547372026600 i=89
1000134600800354781929399250536541864362461089950800 i=90
3935312233584004685417853572763349509774031680023800 i=91
15487357822491889407128326963778343232013931127835600 i=92
60960876535340415751462563580829648891969728907438000 i=93
239993345518077005168915776623476723006280827488229600 i=94
944973797977428207852605870454939596837230758234904050 i=95
3721443204405954385563870541379246659709506697378694300 i=96
14657929356129575437016877846657032761712954950899755100 i=97
57743358069601357782187700608042856334020731624756611000 i=98
227508830794229349661819540395688853956041682601541047340 i=99
896519947090131496687170070074100632420837521538745909320 i=100
3533343320884635898708258511468514257188006702535057407320 i=101
13927547459020991989083038404429289207944958458536245702640 i=102
54906677482678910726192747555923159377475316999998660943100 i=103
216489185503133990863274261791925599831188392742851863147080 i=104
853702637172735926234421145556838686126761775155774328259240 i=105
3366939372774715522158184331074634818182181954352680060985040 i=106
13280705303722489004068393750349948449496384375502238018329880 i=107
52391773216519910749994580850004383791591241114366627044787600 i=108
206709359781542193322705891717290023323187260396682873976707440 i=109
815663960219058384462569194343901173113117297781505394610791520 i=110
3218959557293069695825496284821467129607123621602012360874730820 i=111
12704920022590345879098861442746675573493602966676969141151592440 i=112
50151000089172417943811295168736877263790538026356457136124707000 i=113
197987426438993719534698504405274280676181776208398535128701017200 i=114
781708976802233823680102715669100177152510806064194216284009188600 i=115
3086748267372923303762456877257472494397093952150920751480446539600 i=116
12190039767760866606383939871203238833805472726290924323643119385200 i=117
48145535217206784075634048230802707999063631776107012034556858076000 i=118
190174864107966797098754490511670696596301345515622697536499589400200 i=119
751269297881058917464501210451062751843240026086509499359064493663600 i=120
2968129521136642608343357241290264314659358135849980153205484311031600 i=121
11727731278637465915893265197293239487190634585553580117543620936271200 i=122
46343454246228695957965322150594252812285572152590760141906244022362000 i=123
183149331181095806425878953139148487114152581147038684080813476376374624 i=124
723875928001473901587997767169015449070222106438295751367024692344718752 i=125
2861304849265668492891140780463352404986232263244287143198790516197234752 i=126
11311095732253345760960290897769189975961199415637572612957718759342193629 i=127
44718285453094622775889522153971216184032648852520635911693306722980765510 i=128
176809220945312585436978572208778500912252165463043129681618151197016257478 i=129
699138751524213124094312216825551629561424593205010237977696200916445964684 i=130

[toc] | [prev] | [next] | [standalone]

#127169

num catalan(num  n) 
{num c=1,i;
 if(n>100000u)R (num)0u; 
 F(i=2;i<=n;++i)
   c=((4u*i-2u)*c)/(i+1u); 
 R c;
}

If one want translate the recursive in iterative;
This would Return 0 for error (argument too much big >100000 )
else it should return the Catalan number
of its argument

[toc] | [prev] | [next] | [standalone]

#127079

On 26/2/2018 06:59, jacobnavia wrote:
> I want to do the computation of catalan numbers in 480 bits (my qfloat
> extension to C)
>
> But I would like to do as much calculations in 128 bits only (at the
> start of the series) as possible.
>
> Possible means until before the computation overflows.
>
> How can I know if a multiplication will overflow in 128 bits?

Let the OS tell you? If you could predict those overflows, your C codes 
would not make it happen? :)

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不賭錢! 不援交! 不打交! 不打劫! 不自殺! 不求神! 請考慮綜援 
(CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#127084

Le 26/02/2018 à 16:37, Mr. Man-wai Chang a écrit :
> Let the OS tell you? If you could predict those overflows, your C codes 
> would not make it happen?

I want to calculate where an overflow can occur BEFORE, not afterwards 
when it is too late.

[toc] | [prev] | [next] | [standalone]

#127158

On 27/2/2018 01:33, jacobnavia wrote:
> Le 26/02/2018 à 16:37, Mr. Man-wai Chang a écrit :
>> Let the OS tell you? If you could predict those overflows, your C
>> codes would not make it happen?
>
> I want to calculate where an overflow can occur BEFORE, not afterwards
> when it is too late.

I believe you could just trap the overflow error within your program by 
hooking an interrupt service routine to the overflow signal.

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不賭錢! 不援交! 不打交! 不打劫! 不自殺! 不求神! 請考慮綜援 
(CSSA):

http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

#127159

On 28/2/2018 22:31, Mr. Man-wai Chang wrote:
> On 27/2/2018 01:33, jacobnavia wrote:
>> Le 26/02/2018 à 16:37, Mr. Man-wai Chang a écrit :
>>> Let the OS tell you? If you could predict those overflows, your C
>>> codes would not make it happen?
>>
>> I want to calculate where an overflow can occur BEFORE, not afterwards
>> when it is too late.
>
> I believe you could just trap the overflow error within your program by
> hooking an interrupt service routine to the overflow signal.

As long as you are doing dangerous stunts, you should prepare for it. :)

http://jayconrod.com/posts/33/trapping-floating-point-exceptions-in-linux

https://www.gnu.org/software/libc/manual/html_node/Program-Error-Signals.html

-- 
   @~@   Remain silent! Drink, Blink, Stretch! Live long and prosper!!
  / v \  Simplicity is Beauty!
/( _ )\ May the Force and farces be with you!
   ^ ^   (x86_64 Ubuntu 9.10)  Linux 2.6.39.3
不借貸! 不詐騙! 不賭錢! 不援交! 不打交! 不打劫! 不自殺! 不求神! 請考慮綜援 
(CSSA):
http://www.swd.gov.hk/tc/index/site_pubsvc/page_socsecu/sub_addressesa

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web