Pascal's Triangle Java (performance)

Question

I need to get some information about the Pascal Triangle.

What is a pascal triangle ?

It is a triangle of integers with 1 at the top and at the sides. Any number inside is equal to the sum of the two numbers above his. For example, here are the first 5 lines of the triangle:

So I need to figure out the number of numbers pairs that exist in the first thousand lines of the triangle.

I would like to know how I can improve the performance of my code or rewrite some part that is poorly structured

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;
import java.util.Vector;

public class PascalTriangle {

    private static int [][] matrix;
    private static int i, j, n;

    public static void main(String[] args) 
    { 

        long start_time = System.currentTimeMillis();  

        n = 0; // Number of even numbers;

        matrix = new int[1000][1000]; 

        for (i = 0; i < 1000; i++) {        
            for (j = 0; j < 1000; j++) {
                matrix[i][j] = 0;
            }
        }

        matrix[0][0] = 1;
        matrix[1][0] = 1;
        matrix[1][1] = 1;

        for (i = 2; i < 1000; i++) {        
            matrix[i][0] = 1;
            matrix[i][i] = 1;
            for (j = 1; j < i; j++) {
                matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j];
                if ( matrix[i][j] % 2 == 0 ) {
                    n++;
                }
            }
        }

        System.out.println( "Amount of even numbers = " + n );

        long end_time  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end_time - start_time)));  

    }
}

Expected result:

Amount of even numbers = 448363

Currently taking a time of 00.011 seconds

Answer 1

One array solution

The following algorithm is an improvement on the two array system stated bellow it. Basically, we only need the context of the old previous value (as well as the next value, which goes unmodified), so we copy this value. From there we can set the new end to 1 then start over. This cuts down on the memory overhead. I think you'll see minimal computational improvements as yours was already pretty efficient, but this one takes less memory. I suspect there will be a performance increase where you are dealing with pretty large arrays.

import java.util.Arrays;

class Pascal{

     public static void main(String []args) {
        int toNthLine = 1000;
        int[] row = new int[toNthLine+1];
        int counter = 0;
        int previous;
        row[0] = 1;
        for (int i = 0; i < toNthLine; i++) {
            previous = 1;
            for (int j = 0; row[j+1] != 0; j++) {
                int temp = row[j+1];
                row[j+1] = previous + row[j+1];
                previous = temp;
                if (row[j+1] % 2 == 0)counter++;
            }
            row[i] = 1;
        }
        System.out.println(counter);
     }
}

Answer 2

There is one fairly obvious optimization that should cut your time in roughly half. Pascal's Triangle is symmetric. Take advantage of that with whatever algorithm you are using. Roughly speaking (without checking my end-conditions so do that):

for (j=1;j<i/2;j++)
{
  value = matrix[i-1][j-1] + matrix[i-1][j];
  matrix[i][j] = matrix[i][i-j] = value;
  if (value % 2 == 0) 
    n+=2;
}
if ((2*j==i) && (value%2 == 0))
  n--;

This also shows some minor optimizations that may gain you time. Saving the new value in a separate variable so that you aren't dereferencing the array subscripts repeatedly, especially the check I added outside the loop, should save a little time. The check outside is because most of the way through the half row you want to count two for every even number, but on the specific end condition in the rows with an odd number of values you will double count it and have to subtract it out again. Do that outside the loop to avoid an if statement inside the loop.

@Neil suggested using two arrays instead of a two dimensional array. That may gain you savings by allowing you to set a variable to row1[i] outside the while loop to avoid double subscripting throughout the j loop. However a good compiler may do that optimization for you. Try it with and without.