I have this issue where I need to square line in Pascal's triangle and when it comes to big numbers it only outputs 0

unsigned long sum_squared(const int line){
  unsigned long long n = 2*line;
  unsigned long long  x1 = factorial(line);
  unsigned long long  k = x1*x1;
  unsigned long long  x = factorial(n)/(k);
  return x;

}

unsigned long long factorial(unsigned long long n) {
    if (n == 0){
        return 1;
      }
    return n * factorial(n - 1);
}

I test it with:

printf("%lu\n", sum_squared(14));

CodePudding user response：

1. 28! = 304888344611713860501504000000 which is larger than maximum unsigned long long 18446744073709551615. It wraps over (modulo ULLONG_MAX)and the result is smaller than k. The division will be 0
2. You use the wrong printf format.

unsigned long long factorial(unsigned long long n) 
{
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

unsigned long sum_squared(const int line)
{
  unsigned long long  n = 2*line;
  unsigned long long  x1 = factorial(line);
  unsigned long long  k = x1*x1;
  unsigned long long  x = factorial(n)/(k);

  printf("%llu %llu %llu %llu %llu\n", n, x1, k, x , factorial(n));
  return x;

}

int main(void)
{
    printf("%llu\n", sum_squared(14));
}

output:

28 87178291200 18442642257371725824 0 12478583540742619136
18417982275456073728

CodePudding user response：

The key word here is "outputs". You need the correct format specifier to output unsigned long long: %llu.

CodePudding user response：

The maximum number should be 7219428434016265740 and it equals sum_squared(33)

The code tries to evaluate the sum using (directly) the formula

⎛ 2n ⎞   (2n)!
⎜    ⎟ = ⎯⎯⎯⎯⎯
⎝  n ⎠   n!·n!

As noted in the other answers and comments, this leads to overflow of the intermediate results.

Luckily, this expression can be simplified and evaluated safely (without overflowing 64-bit wide unsigned integers) up to the required value.

We can start dividing both the numerator and the denominator by n!

(2n)!   (n 1)·(n 2)· ... ·(n n)   (n 1)·(n 2)· ... ·(2n-2)·(2n-1)·(2n)
⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
n!·n!             n!                   1·2· ... ·(n-1)·n

Also note that the higher half terms in the denominator have the corresponding doubles in the numerator. Let's see a couple of examples

⎛ 8 ⎞    8!     5·6·7·8   5·2·7·2
⎜   ⎟ = ⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯ = 70
⎝ 4 ⎠   4!·4!   1·2·3·4     1·2

⎛ 10 ⎞    10!    6·7·8·9·10   2·7·2·9·2         70
⎜    ⎟ = ⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯ = 252 = ⎯⎯ · 9
⎝  5 ⎠   5!·5!   1·2·3·4·5       1·2             5

⎛ 12 ⎞    12!    7·8·9·10·11·12   7·2·9·2·11·2         252
⎜    ⎟ = ⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ = ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ = 924 = ⎯⎯⎯ · 11
⎝  6 ⎠   6!·6!    1·2·3·4·5·6        1·2·3              3

Now we can derive a couple of recurrence relations that let us evaluate the sum at a given n from the sum at n - 1

sum(1) = 2

         sum(n-1) 
sum(n) = ⎯⎯⎯⎯⎯⎯⎯⎯ · (2·n - 1)          when n is even
            n/2

         sum(n-1) 
sum(n) = ⎯⎯⎯⎯⎯⎯⎯⎯ · (2·n - 1) · 2      when n is odd
            n

Note that the divisions (which are always exact, but I won't demonstrate that) are performed before the multiplications, avoiding unnecessary overflows.

Those formulas produce the following sequence

  1                      2
  2                      6
  3                     20
  4                     70
  5                    252
  6                    924
  7                   3432
  8                  12870
  9                  48620
 10                 184756
 11                 705432
 12                2704156
 13               10400600
 14               40116600
 15              155117520
 16              601080390
 17             2333606220
 18             9075135300
 19            35345263800
 20           137846528820
 21           538257874440
 22          2104098963720
 23          8233430727600
 24         32247603683100
 25        126410606437752
 26        495918532948104
 27       1946939425648112
 28       7648690600760440
 29      30067266499541040
 30     118264581564861424
 31     465428353255261088
 32    1832624140942590534
 33    7219428434016265740

The next value, 34, can't be calculated this way.