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 1 of 3  [1] 2 3  Next page →

#127049 — Catching overflow

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

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.

So I conclude that (assuming a function that searches the first non-zero 
bit called "bsr") the test should be:

	if ((64 - bsr(A))  + (64 - bsr(B))) > 88)
		break;

The "bsr" function is just a single asm instruction in ARM64 (and also 
in the x86). That would be a very efficient test.

Do I have a bug somewhere?

Thanks in advance for your review.

[toc] | [next] | [standalone]

#127055

On 25/02/18 23: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)
> 
> 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.
> 
> So I conclude that (assuming a function that searches the first non-zero 
> bit called "bsr") the test should be:
> 
>      if ((64 - bsr(A))  + (64 - bsr(B))) > 88)
>          break;
> 
> The "bsr" function is just a single asm instruction in ARM64 (and also 
> in the x86). That would be a very efficient test.
> 
> Do I have a bug somewhere?
> 
> Thanks in advance for your review.

You are close - but it is even easier than you think.  log(pow(2, 128)) 
is just 128, not 88.  I don't know the "bsr" instruction - check that it 
is going in the right direction (MSB or LSB first).

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

#127061

Le 26/02/2018 à 00:32, David Brown a écrit :

> You are close - but it is even easier than you think.  log(pow(2, 128)) 
> is just 128, not 88.  I don't know the "bsr" instruction - check that it 
> is going in the right direction (MSB or LSB first).
> 
> 

Ahhhh yes, I knew I had a bug somewhere. Of course. not 88 but 128. 
That's the test.

Thanks

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

#127059

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

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

#127060

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

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

#127063

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

> 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

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.

-- 
Ben.

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

#127070

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.

I have already optimized that, without a table but just computing all 
catalan numbers less than 63 in 128 bits, what goes very fast.

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

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/

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.

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

#127076

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.

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

#127085

Le 26/02/2018 à 16:21, Ben Bacarisse a écrit :
> I don't follow this but then I don't know what algorithm you are using.

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

// A Binomial coefficient based function to find nth catalan
// number in O(n) time
unsigned __int128  catalan(unsigned __int128 n)
{
     // Calculate value of 2nCn
    unsigned  __int128  c = binomialCoeff(2*n, n);

     // return 2nCn/(n+1)
     return c/(n+1);
}

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

#127106

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.

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

#127112

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.

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

#127121

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.  In that case, an algorithm that avoids
divisions is to be preferred (if speed matters) - divisions often have a
lot higher latency and stall pipelines in processors.

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

#127311

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

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

#127316

On Saturday, March 3, 2018 at 3:17:57 AM UTC-7, 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 ).



Why does James Kuyper focus on his own ego so much? Nobody is being controlled by a corporation. Undeniably, the top thing that concerns James Kuyper is seeming "moral", and if he can not have that he will flood to slap truly honest people down... there is no way to stop him. 

Is this for real? Autumn Nissen's computer has more hard drives than James Kuyper's. Autumn Nissen wins. James Kuyper loses. Simple as that. That's what James Kuyper does when he gets caught. He of course creates a flood, starts a new thread so he can claim he didn't do it. Don't blame me it was my left hand... and then he babbles to himself with his right hand. 



--
My Snoring Solution!
http://www.5z8.info/trojan_p4g1zy_how-to-skin-a-gerbil
https://www.youtube.com/playlist?list=PLU_evUKollmjeuJy5V5UMotPUs65Q7YM6
https://youtu.be/u4xD43Khhkw
Jonas Eklundh Communication

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

#127317

This not calculate factorial of any
(n is the input)
 F(i=2,c=1;i<=n;++i) 
   c=((4u*i-2u)*c)/(i+1u);
each (4u*i-2u)*c would be divisible for i+1

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

#127319

On Saturday, March 3, 2018 at 4:20:53 AM UTC-7, asetof...@gmail.com wrote:
> This not calculate factorial of any
> (n is the input)
>  F(i=2,c=1;i<=n;++i) 
>    c=((4u*i-2u)*c)/(i+1u);
> each (4u*i-2u)*c would be divisible for i+1



Yup. Unfortunately this is what we have to face. Trolls who clearly have no reason for being here other than to upset me. 

So, yeah, I buy into my own inner world, fully knowing it's fake, because it makes me reconsider my program, improving it. 

By the way, spending time maybe researching a problem isn't a waste. Insisting you know everything and trying to convince people that it's true? *That* is a waste ;) Hell, just recently he was declaring himself the only "true Linux advocate", and claiming that "advocates" (in satire-quotes just to annoy Autumn Nissen) are focusing on Windows more than on Linux. 

I am happy the person you are referencing is in my kill filter. Kevin S Jervik calls it "attacking" him, even though he proceeds to trigger that precise response. 

Linux offers the least of any of the competition. 



--
My Snoring Solution!
https://youtu.be/Z5wo5aE7MUk
https://www.youtube.com/watch?v=u4xD43Khhkw
Jonas Eklundh Communication AB

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

#127350

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

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

#127351

I don't Know what big O you speak about, the computer can compute in few second Catalan number for 100000 as argument here whit algo posted (100001 is here error)

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

#127626

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

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

#127627

On 2018-03-11, Ike Naar <ike@iceland.freeshell.org> wrote:
> Right. Just for fun, here's a toy program that computes n Catalan
> numbers in O(2^n) time, using Pascal's triangle.

s/2^n/n^2

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web