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

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();

while (noOfTestCaseT != 0){
noOfTestCaseT--;
long firstElement = Long.parseLong(inputAandD[0].trim());
long commonDifference = Long.parseLong(inputAandD[1].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)?

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.45: total time

100 test case
0.14: bringing up the JVM
0.02: parsing the input and generating output
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;
}

• Thank you so much for such detailed explanation :) . The algorithm that i used is [Exponential by Squaring]( en.wikipedia.org/wiki/Exponentiation_by_squaring ). using the fact that D^ (-1) wrt P = D^(P-2 )% P – Ankur Anand Jun 8 '15 at 11:48
• Btw i've one question how do you do the benchmark .. what is the tool you uses .. i tried with Google Caliper .. followed the documentation but not able to do it .. if possible for you could help me and give some link or way from where i get how to do proper benchmark of the code .. Thanks :) – Ankur Anand Jun 8 '15 at 11:57
• @AnkurAnand My benchmarking isn't very accurate unfortunately. I am just running time java program < input.txt > out from the command line. So it isn't very accurate. But I wonder if the programming challenge people do anything different than that? As I said before, your exponential by squaring vs the one I listed are almost the same in terms of run time. I wouldn't worry about switching from one to another. – JS1 Jun 8 '15 at 17:39
• Shameless plug ... you can use the Microbench tool to perform micro-benchmarks, but I suspect the functions run faster than the nanosecond 'step' counts for the computer, so you will have to batch them. Also, I believe you can also treat the process as two arithmetic progressions, one is N = nd + a and the other is N = mp + 0 and then solve their intersection: en.wikipedia.org/wiki/Chinese_remainder_theorem – rolfl Jun 9 '15 at 11:50