StackOverflow error while filling int[2000][2000] with a logic

Question

I need to fill a int[2000][2000] matrix with some logic.

My code for filling array:

// n: (1 to 2000)
for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
        uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;
    }
}

Here: i * j * i * j is my take on getting square of i*j. The calc() is a method used to get a value. Then, I check if value returned by calc() is even or odd. If it is even, I store 0 in matrix on (i, j), otherwise I store 1 in it.

My calc() function is as below:

private static int calc(int n){

    // value of n=calc(1 | 2 | 3) is known
    if(n < 4) return n;

    // if value is present in HashMap, return it (don't calculate again)
    if(map.containsKey(n)) {
        return map.get(n);
    }

    // calculate the answer
    int answer = 1 * calc(n-1) + 2 * calc(n-2) + 3 * calc(n-3);

    // store it in HashMap so that we don't have to recalculate it
    map.put(n, answer);

    return answer;
}

---

Now, If n is 13, it creates a [13x13] matrix. But, for n=14, it throws a StackOverflowError at map.containsKey(n). I need to be able to make [2000x2000] matrices.

I know that the problem might be recursion. But, is there a way around this? Can I do something with BitSets(I don't have a clue on how to do it)?

I can use other datatype matrices: String[][] or boolean[][] too. I can't use a library outside Java SDK/JDK.

Edit: It is not a duplicate of "What is StackOverflowError?", I know what it is, I know why they occur. I need help in finding an alternative to my approach to prevent this error.

Answer 1

You cannot calculate calc for the range of values that you need. At i = j = 216 you get an integer overflow (the result of i * j * i * j becomes negative), and so the result of calc would likely be incorrect. Worse, your memoization map would explode in size as well.

The good news is that you don't actually need to calculate it. Look at this expression:

uniMatrix[i][j] = (((calc(i * j * i * j)) & 1) == 0) ? 0 : 1;

You don't need the calculated value, all you need to know is if the value is even or odd. And you can know that, using simple math. The heart of the calc implementation is this:

int answer = calc(n - 1) + 2 * calc(n - 2) + 3 * calc(n - 3);

And we know that the first 3 values are 1, 2, 3. In fact it's enough to know that they are odd, even, odd. The values that will follow after can be calculated based on simple math:

• Multiplying any number by 2 will be even
• Multiplying any number by 3 will remain what it was (odd if it was odd, even if it was even)
• Adding an even number of odd numbers will be an even number
• Adding an even number to any other number will have the even-ness of the other number

Now, let's see the first couple of values calculated by calc, and verify the logic of deciding if the value will be odd or even:

• 0 -> 0 : even (given)
• 1 -> 1 : odd (given)
• 2 -> 2 : even (given)
• 3 -> 3 : odd (given)
• 4 -> 10 : even, because odd + even + odd is even
• 5 -> 22 : even, because even + even + even is even
• 6 -> 51 : odd, because odd + even + even is odd
• 7 -> 125 : odd, because even + even + odd is odd
• 8 -> 293 : odd, because even + even + odd is odd
• 9 -> 696 : even, because odd + even + odd is even
• 10 -> 1657 : odd, because odd + even + even is odd
• 11 -> 3928 : even, because odd + even + odd is even
• 12 -> 9330 : even, because even + even + even is even
• 13 -> 22157 : odd, because odd + even + even is odd
• 14 -> 52601 : odd, because even + even + odd is odd
• 15 -> 124905 : odd, because even + even + odd is odd
• 16 -> 296578 : even, because odd + even + odd is even

If you notice, a repeating pattern has emerged:

even odd even even odd odd odd

Only 0 breaks the pattern, in which case the value is given as 0. As such, your implementation can be rewritten as this, with no risk of stack overflow:

int[] pattern = {0, 1, 0, 0, 1, 1, 1};
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        long x = (long) i * j * i * j;
        if (x < 2) {
            uniMatrix[i][j] = (int) x;
        } else {
            uniMatrix[i][j] = pattern[(int)((x - 2) % pattern.length)];
        }
    }
}

For 0, since it doesn't follow the pattern, an exceptional treatment is necessary. For 1, x - 2 would be negative. Since the correct value for 0 and 1 is itself, the if (x < 2) branch is an easy way to treat these cases.

Answer 2

we are just interested in the result modulo 2 so all the calculations can be done modulo 2. The recursion reduces then to (writing calc' for calc modulo 2):

calc'(1) = 1
calc'(2) = 0
calc'(3) = 1
calc'(n) = (calc'(n-1) + calc'(n-3)) % 2

So we see that the next value depends only on two previous values in fixed distance and since the range of numbers for each value is finite (can be only 0 or 1), we know the sequence must be eventually periodic. A little experimentation shows the period is 7.

So the values modulo 2 are (for n >= 1):

calc'(n) = 
     1 if n%7 = 1,
     0 if n%7 = 2,
     1 if n%7 = 3,
     0 if n%7 = 4,
     0 if n%7 = 5,
     1 if n%7 = 6,
     1 if n%7 = 0.