Thread: 2d Array and a SegFault

Hello everyone. I'm encountering a segmentation fault in the following code for large values of SIZE. It executes as expected when SIZE equals 1000. But when SIZE equals 10000, I get a segfault.

Does anyone know why I am receiving this segmentation fault?

Code:

void populate_grid(unsigned int size, unsigned long long grid[][size]){
   unsigned int i, j;


   //seed the grid with a few values
   for(j = 0;j < size;j++)
   {
      grid[0][j] = j + 1;
      grid[j][j] = 1;
   }


   //use n choose r recurrence relation
   for(i = 1;i < size;i++)
      for(j = i + 1;j < size;j++)
         grid[i][j] = grid[i][j - 1] + grid[i - 1][j - 1];


}

main.c

Code:

#define SIZE 10000


int main(){
   unsigned long long grid[SIZE][SIZE];


   populate_grid(SIZE, grid);
//   out(SIZE, grid);


//   choose(50, 20, SIZE, grid);


   return 0;
}

Upon some further research, it appears I am overflowing my OS stack. I appended the qualifier static to the array in main and this solved the issue.

Or better, use malloc() to dynamically allocate the memory on the heap.

rstanely - yes that is the plan for the next version. Thank you!

So I've written a brute-force approach to compare the two version's performance. But now I've encountered a floating point exception, and I'm not sure where it is occurring. Again the error only occurs on "large-ish" values of size. It works as expected for size equals 50, but generates the floating point exception at size equals 70.

Code:

unsigned long long factorial(unsigned int n){
   unsigned long long i, value;
   for(i = value = 1;i <= n;i++)
      value *= i;
   return value;
}


void populate_grid(unsigned int size, unsigned long long grid[][size]){
   for(unsigned int i = 0;i < size;i++)
      for(unsigned int j = i;j < size;j++)
         grid[i][j] = factorial(j + 1) / (factorial(i + 1) * factorial(j - i));
}

If this is another Project Euler problem (which one?) then you should analyze the calculation you're doing since it seems to me you might be able to do it without calculating factorials at all.

If you really need giant numbers, you can use a "big number" library like https://gmplib.org/

Haha algorism, nice to see you poking around my thread. It IS indeed a project euler problem (https://projecteuler.net/problem=53). My approach is to use my recurrence relation above (first populate_grid() function posted) to generate n choose r values for a fixed r while looping through n (thus avoiding using factorials). Once I reach an n for a given r that outputs a value greater than or equal to one million, I can stop generating choose values for that particular r and calculate how many n's for that particular r produce a 'n choose r' value at or above one million. I believe my answer is a few lines away, but I got sidetracked by my exceptions!

I often find myself too concerned with the decimal value project euler wants instead of learning from my errors along the way. If you would like to take a gander at the next problem I plan on solving, here it is.

https://projecteuler.net/problem=101

The issue I'm having with problem 101 is finding the right linear algebra library to use. I've been struggling with GSL CBLAS. My solution involves interpolating the data to form the desired n'th degree polynomial with an Ax=b matrix-vector equation for n = 1,2,...,10. Obviously I can solve this by hand, in relatively trivial time, but I'm treating it as an exercise in coding linear algebra problems. But I digress... I will start a new thread for that guy once I get started on that problem.

If the answer to problem 53 is 4075 then I have a 20 line solution that uses only 32-bit ints. It takes advantage of pascal's triangle and constrains maximum values to 1000001.

Problem 101 looks like a doozy!

Code:

void solve53(unsigned int size, unsigned int grid[][size], unsigned int ceiling){


   int i, j, sum = 0;


   //seed the grid with a few values
   for(j = 0;j < size;j++)
   {
      grid[0][j] = j + 1;
      grid[j][j] = 1;
   }


   //use n choose r recurrence relation
   for(i = 1;i < size;i++)
      for(j = i + 1;j < size;j++)
      {
         if((grid[i][j] = grid[i][j - 1] + grid[i - 1][j - 1]) > ceiling)
         {
            sum += size - j;
            break;
         }
      }
   printf("%d\n", sum);
}

Ahh yes, it is Pascal's triangle. I was using using a combinatoric identity from my textbook and didn't realize it essentially generates the triangle. Pretty neat. I assume our solutions are somewhat similar? And yes! You've got the correct answer.

Originally Posted by John...

I assume our solutions are somewhat similar?

Similar in some ways, different in others. I like the way you took advantage of the fact that once a value was over 1000000, the rest of the values on that line (up to the middle) will also be over 1000000.

The only advantage of mine is that I only store a single line of the triangle. Combining both ideas may yield an optimal solution!

Code:

#include <stdio.h>

#define MAXVAL  1000000
#define MAXLINE 100

int main(void) {
    int n[MAXLINE] = {1, 1};  // line 1 of Pascal's triangle
    int cnt = 0;

    for (int line = 2; line <= MAXLINE; line++) {
        int prev = 1; // first number is always 1
        for (int i = 1; i < line; i++) { // start at 2nd number
            int r = prev + n[i];
            if (r > MAXVAL) {
                cnt++;
                r = MAXVAL;  // constrain value size
            }
            prev = n[i];
            n[i] = r;
        }
        n[line] = 1; // last number is always 1
    }

    printf("%d\n", cnt);
    return 0;
}

BTW, I was able to solve 101 in about 40 lines using a little trick. No external libraries needed.

BTW, I was able to solve 101 in about 40 lines using a little trick. No external libraries needed.

Well, that is very interesting. Did you still use linear algebra concepts and just implement your own routine(s)?

Originally Posted by John...

Well, that is very interesting. Did you still use linear algebra concepts and just implement your own routine(s)?

No linear algebra (unless it's somehow implied in the method).

Here's the idea applied to the n-cubed example.

The first row is the values of the function. The subsequent rows are the differences between each pair of values in the previous row. Keep going until you get 0's (the previous row is all the same value).

Code:

1   8  27  64  125
  7  19  37  61
   12  18  24
     6    6
        0

Working back up from that point gives us the next value in the original sequence:

Code:

1   8  27  64  125    216
  7  19  37  61     91
   12  18  24    30
     6    6    6
        0

To get the so-called FITs, just add one value at a time:

Code:

1                = 1

1   8         +7 = 15
  7

1   8   27    +31 = 58
  7   19      +12 = 31
    12

1    8    27    64   +61 = 125   (the correct answer)
  7    19    37      +24 = 61
    12    18         +6 = 24
       6

You get the correct answer when you have enough values in the initial sequence to reach the row with repeated values. The FITs are 1, 15 and 58.

Wow. That is amazing. I have no idea how this works. What kind of method would you call this? Do you know of any sort of proof or reason why this should produce fits so nicely?

Apparently it's called "the method of common differences".
Sequences: The Method of Common Differences

Okay, so what I gather is that the method of common differences allows one to be able to estimate the degree of the polynomial of the generating function accurately. We do this by taking differences of successive known terms in the sequence until we come across a row with all same values. Apparently, calculus is a way of understanding why, if it takes until the n-th row to produce a row with all same values, the polynomial is n-th degree. I've studied calculus, and I don't quite see the reasoning.

And this is all well and good, but I still don't see how this generates FIT's that should be produced by bad generating functions.

I don't know about your math background, but do you know of the calculus explanation the page speaks of? Also any ideas about the FIT's in particular? Sorry for the barrage of questions, but I find your solution so very awesome and I wish to understand.