First index of number in the arithmetic progression (which is multiple of prime)

Question

Things to deal with this problem.

1. An infinite Arithmetic progression.
2. A prime number. - p.
3. The starting number of an Arithmetic Progression. - a.
4. Common difference in the arithmetic progression given to him. - d.

You have to print the first index of a number in that Arithmetic Progression, which is a multiple of the given prime number, p.

Input format: The first line contains a number, tc, denoting the number of test cases. After that follow tc number of test cases, each is 2 lines - the first contains two integers, a and d - a depicts the first term in the AP, d depicts the common difference. The next line contains the prime number.

Output format: You have to print the FIRST index (0-based) of the multiple of the given prime number in the given AP. If no such element exists in this infinite AP, then print -1.

Constraints: 0 <= a, d, <= 10^18 1 <= p <= 10^9

My code:

public static void main(String[] args) throws NumberFormatException, IOException{
StringBuilder output = new StringBuilder();
        BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
            int noOfTestCaseT=Integer.parseInt(reader.readLine().trim());

            while (noOfTestCaseT != 0){
                noOfTestCaseT--;
                String[] inputAandD = reader.readLine().split(" ");
                long firstElement = Long.parseLong(inputAandD[0].trim());
                long commonDifference = Long.parseLong(inputAandD[1].trim());
                long primeNo = Long.parseLong(reader.readLine().trim());
                firstElement %= primeNo;
                commonDifference %= primeNo;
                int result = 0;
                if(commonDifference == 0) output.append(-1);
                else if (firstElement == 0) output.append(0);
                else{
                    long inverseMod =  getPowerValue(commonDifference, primeNo);
                    result = (int) ((inverseMod * (primeNo-firstElement)) % primeNo) ;
                    output.append(result);
                }
                output.append("\n");

            }

            System.out.println(output);
    }


    private static long getPowerValue(long base, long primeNo) {
        long exp = primeNo -2;
        long powerResult = 1;
        while (exp > 0){
            if ((exp & 1) == 1) powerResult = (powerResult * base) % primeNo;
            base = (base * base) % primeNo;
            exp = exp >> 1 ;
        }
        return powerResult;
    }

How could I can optimize this code further so that its performance improves (though the solution is within the given time limit and I really want to know what are the possible improvement I can make)?

Answer 1

Time elapsed is almost all in overhead

I'm not sure you can do any better than what you've done. I tested your program and it ran extremely fast. In fact, I determined that most of the time was probably being spent bringing up the JVM. I ran your program with varying test inputs (up to 100000 test case input), and also ran your program without computing the result (just reading the input and outputting one number per test case). The timings showed that most of the time was being spent just bringing up the JVM (or some other Java related overhead):

100000 test case (times are in seconds)
0.14: bringing up the JVM
0.19: parsing the input and generating output
0.12: calculating the answer
0.45: total time

100 test case
0.14: bringing up the JVM
0.02: parsing the input and generating output
0.01: calculating the answer
0.17: total time

So I believe that your actual algorithm runs for about 0.01 seconds out of 0.17 total time.

C program was faster (less overhead?)

I converted your program to C and tested it to see if it would run any faster. It did run faster, probably because of the lack of overhead:

100000 test case (C program)
0.29: total time

100 test case (C program)
0.01: total time

Here is the C program, just to show you that it is exactly the same as your java program:

#include <stdio.h>

static long long getPowerValue(long long base, long long primeNo);

int main(void)
{
    int noOfTestCaseT = 0;
    long long firstElement, commonDifference, primeNo;

    scanf("%d", &noOfTestCaseT);

    while (noOfTestCaseT != 0){
        noOfTestCaseT--;
        scanf("%lld %lld %lld", &firstElement, &commonDifference, &primeNo);
        firstElement %= primeNo;
        commonDifference %= primeNo;
        if(commonDifference == 0) puts("-1\n");
        else if (firstElement == 0) puts("0\n");
        else {
            long long inverseMod = getPowerValue(commonDifference, primeNo);
            int result = (int) ((inverseMod * (primeNo-firstElement))%primeNo);
            printf("%d\n", result);
        }
    }
    return 0;
}

static long long getPowerValue(long long base, long long primeNo)
{
    long long exp = primeNo -2;
    long long powerResult = 1;
    while (exp > 0){
        if ((exp & 1) == 1) powerResult = (powerResult * base) % primeNo;
        base = (base * base) % primeNo;
        exp = exp >> 1 ;
    }
    return powerResult;
}

A slightly faster inverse mod function

From wikipedia, I copied this algorithm for finding the inverse mod. Supposedly, it is slightly faster than the algorithm you are using. Using the 100000 test case input, I found that it was a little bit faster, but not by much (maybe 10% faster). Here is the function (it replaces your getPowerValue function):

private static long inverse(long a, long n)
{
    long t    = 0;
    long newt = 1;
    long r    = n;
    long newr = a;

    while (newr != 0) {
        long quotient = r / newr;
        long tmp;

        tmp  = newt;
        newt = t - quotient * newt;
        t    = tmp;

        tmp  = newr;
        newr = r - quotient * newr;
        r    = tmp;
    }
    if (t < 0)
        t += n;
    return t;
}