I am currently studying linear congruential generators, and there was an example in which I didn't get the code:
public class Random {
static final int a = 48271;
static final int p = 2147483647; //2^31 - 1
static final int q = p/a;
static final int r = p%a;
int state;
public Random() {
this ( (int)(System.currentTimeMillis()%Integer.MAX_VALUE ));
}
public Random(int initialValue) {
if (initialValue < 0)
initialValue += p;
state = initialValue;
if (state == 0)
state = 1;
}
public int randomInt() {
int tmp = a * (state % q) - r * (state/q); //line I don't get
if (tmp < 0)
state = tmp+p;
else
state = tmp;
return state;
}
}
The teacher said that it was so that all numbers can be expressed in 32 bits (or somethig like that). The thing is that a LCG should have a period of exactly $p-1$ and I don't get why it should be the case with this line.
Could you also explain why the following code would not work?
public int randomInt() {
int tmp = (a*state)%p;
if (tmp <= 0) state = tmp+p;
else state = tmp;
return state;
}
Thanks in advance for any answer.
Edit: I compared both generators by generating numbers in the interval $]0,1[$ with the following codes:
//Generators
public int randomInt() {
int tmp = (a*state)%p;
if (tmp <= 0) state = tmp+p;
else state = tmp;
return state;
}
public int randomInt2() {
int tmp = a * (state % q) - r * (state/q);
if (tmp < 0) state = tmp+p;
else state = tmp;
return state;
}
public double randomReal() {
return randomInt()/(double)p;
}
public double randomReal2() {
return randomInt2()/(double)p;
}
And the Main method:
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
public class Main {
public static void main(String[] args) {
File file = new File("resultatsGC.xls");
FileWriter fw = null;
Random rand = new Random();
Random rand2 = new Random();
double x, y;
int[] tab = {0,0,0,0,0,0,0,0,0,0};
int[] taby = {0,0,0,0,0,0,0,0,0,0};
try {
for (int i = 1 ; i < Math.pow(2, 31)-1 ; i++) {
x = rand.randomReal();
y = rand2.randomReal2();
for (int j = 0 ; j < 10 ; j++) {
if (x > j/(double)10 && x < (j+1)/(double)10) {
tab[j]++;
}
if (y > j/(double)10 && y < (j+1)/(double)10) {
taby[j]++;
}
}
if (i%100000000 == 0)
System.out.println(i+") "+x);
}
fw = new FileWriter(file, false);
//Write in file the results
for (int i = 0 ; i < 10 ; i++) {
double a = ((double)i)/10;
double b = ((double)(i+1))/10;
String str = "["+a+";"+b+"]\t";
fw.write(str);
fw.write(tab[i]+"\t");
fw.write(taby[i]+"\n");
}
fw.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
if (fw != null)
fw.close();
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("DONE!");
}
}
}
And here is what it graphically gives:
Orange columns are the results of the algorithm that I had a question about. Clearly, it is better (much more uniform), but my question remains: why is it correct (even more correct than the other)?