How to optimize population projections for speed?

Question

I am currently working on a problem of an online judge (not a contest). The program must calculate how many years will require for the population A (which is always less than B) to be higher than B. If the time is more than a Century then print "More than a century" in Portuguese.
Input

1
90000 120000 5.5 3.5

Where 1 is the number of test cases and in the next line are the population of A, population of B, percentage growing rate of A and percentage growing rate of B. For this input the result will be 16 years.

However, my code keeps exceeding the time limit, which is only 1 second. I have used Scanner and System.out.print() however I have been told that such methods will make my code slower and will consume more memory, that is way I buffered the input and output. I cannot use types such as long or int as the data stored the variables is longer than those values.

import java.io.*;
import java.math.BigDecimal;

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException{
        java.io.InputStreamReader iSR = new java.io.InputStreamReader(System.in);
        java.io.BufferedReader bR = new java.io.BufferedReader(iSR, 16 * 1024);
        BufferedWriter bW = new BufferedWriter(new OutputStreamWriter(System.out));
        String tL;
        BigDecimal PRA = BigDecimal.ZERO, PRB = BigDecimal.ZERO, PA = BigDecimal.ZERO, PB = BigDecimal.ZERO;
        int input = Integer.parseInt(bR.readLine());
        for(int j = 0; j < input; j++){
            tL = bR.readLine();
            String [] = arr = tL.split(" ");
            PA = BigDecimal.valueOf(Integer.parseInt(arr[0]));
            PB = BigDecimal.valueOf(Integer.parseInt(arr[1]));
            PRA = BigDecimal.valueOf(Double.parseDouble(arr[2]));
            PRB = BigDecimal.valueOf(Double.parseDouble(arr[3]));
            PRA = PRA.divide(BigDecimal.valueOf(100)); PRA = PRA.add(BigDecimal.ONE);
            PRB = PRB.divide(BigDecimal.valueOf(100)); PRB = PRB.add(BigDecimal.ONE);
            int i = 1;
            while(PA.compareTo(PB) < 0 && i < 103){
                BigDecimal ibd = BigDecimal.valueOf(i);
                PA = PA.multiply(PRA).multiply(ibd);
                PB = PB.multiply(PRB).multiply(ibd);
                i++;
            }
            i--;
            if(i > 100) bW.write("Mais de 1 seculo.\n");
            else bW.write(String.valueOf(i) + " anos.\n");
            bW.flush();
        }
    }
}

Answer 1

First, the syntax error:

        String [] = arr = tL.split(" ");

You probably meant

        String[] arr = tL.split(" ");

Now, let's make all of your variable names readable. Longer names take the same amount of time to access:

    java.io.InputStreamReader inputStream = new java.io.InputStreamReader(System.in);
    java.io.BufferedReader reader = new java.io.BufferedReader(inputStream, 16 * 1024);
    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    String input;
    BigDecimal GrowthA, GrowthB, PopulationA, PopulationB; //no need to assign initial values to them; the values are never used
    int repetitions = Integer.parseInt(reader.readLine());

Now, as always, choosing a better algorithm is a far bigger deal than small things such as your particular means of input and output. On my computer, the code between input = reader.readLine(); and writer.flush(); takes 6 milliseconds to run once and 24 milliseconds to run 50 times for the example input you gave; make sure that your timing measurement does not include the amount of time it spends waiting for you to enter input. For your algorithm, you have chosen to iteratively simulate each year of population growth; this is mathematically inefficient. Your problem algebraically reduces to

PA*(1+PRA/100)^t>PB*(1+PRB/100)^t, solve for t. 
=PA*((PRA+100)/100)^t>...
=PA*(PRA+100)^t*(1/100)^t>...
PA*(PRA+100)^t>...
ln(PA)+t*ln(PRA+100)>ln(PB)+t*ln(PRB+100)
t(ln(PRA+100)-ln(PRB+100))>ln(PB)-ln(PA)
t>(ln(PB)-ln(PA))/(ln(PRA+100)-ln(PRB+100)) (assuming PRA > PRB)

It will be much faster to just use this one computation, and as bonus you will get more precise answers. Also, since you will not be increasing your numbers exponentially in your algorithm, you will now be able to directly use Integer.parseInt instead of having to ever make BigDecimals.

Marginal changes: Testing reveals that using final local variables is faster than reusing larger-scope variables, and that using BufferedReader and BufferedWriter does not create any significant difference in performance (at least on my machine), so unless you test it and get a different result you should use Scanner and System.out just because it's simpler. Also, you should mark all variables that are never modified as final.

    final Scanner scanner = new Scanner(System.in);
    final int repetitions = scanner.nextInt();
    scanner.skip("\n");
    for(int j = 0; j < repetitions; j++){
        final String input = scanner.nextLine();
        final String[] arr = input.split(" ");
        final double PopulationA = Double.parseDouble(arr[0]);
        final double PopulationB = Double.parseDouble(arr[1]);
        final double GrowthA = Double.parseDouble(arr[2]);
        final double GrowthB = Double.parseDouble(arr[3]);
        System.out.print((Math.log(PopulationB)-Math.log(PopulationA))/(Math.log(GrowthA+100)-Math.log(GrowthB+100)) + " anos.\n");
    }

If integer output is required, throw in a call to Math.ceil. On my machine, the code after final String input = scanner.nextLine(); runs once in 3 milliseconds, 50 times in 6 milliseconds, and 10,000 times in 450 milliseconds, with your example input. A doubling of speed for one run, and faster and faster for the same input repeated.

Answer 2

1. The code prints a short line in every iteration and forces the BufferedWriter to flush in every iteration. It just makes no sense to buffer such small amount of data. I would move the flushing outside the for loop. I'm not sure that it will help at all (since you are writing to the standard output) but I guess it would help if you redirect the output to a file.

2. The tL variable could be declared inside the loop. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

3. BigDecimal.valueOf(100) is used and created multiple times. You could create a constant for it. Although the JVM might already optimize it for you it would be readable.

4. I'd put the variable declarations to separate lines. From Code Complete, 2nd Edition, p759:

   With statements on their own lines, the code reads from top to bottom, instead of top to bottom and left to right. When you’re looking for a specific line of code, your eye should be able to follow the left margin of the code. It shouldn’t have to dip into each and every line just because a single line might contain two statements.