# Linear congruential generator with uniform distribution [closed]

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)?

• Although the code is expressed in Java, it's not langauge dependent so I think this is a reasonable question. It would be even better, though, if the Java were replaced by pseudocode. – David Richerby Oct 26 '14 at 20:10
• Perhaps you could try to code both versions and see whether they agree. – Yuval Filmus Oct 26 '14 at 21:47
• Sorry for the Java version, I actually copy-pasted it from the class notes (where the codes are in Java). I did not think about writing pseudo code. Nevertheless, I think Java is quiet easy to understand, even for someone who never learned it. @YuvalFilmus Tried both version and put the results. Why is the method randomInt2() (in the edited part) better? – Laurent Hayez Oct 30 '14 at 19:42
• I agree that Java is easy to understand, and still, I am not planning to read any Java code. Pseudocode would simply be much shorter and even easier to understand. – Yuval Filmus Oct 30 '14 at 20:01
• Also, I can't tell what your question is. Can you please edit the question to be clearer about what your question is. "I didn't get the code" is not a question. – D.W. Nov 30 '14 at 19:57

## 1 Answer

One issue with your generator is that when computing tmp = (a*state)%p, you are actually taking modulo twice: first modulo $2^{32}$ (with sign), then modulo $2^{31}-1$. So you aren't really computing $a^t \pmod{p}$ like you might have expected. To test this hypothesis, you can ask Java to use long for the multiplication a*state – the results should improve. There is also a difference between using signed and unsigned arithmetic, though you can't test this in Java.

The other generator is more careful - it's only multiplying small numbers (the result is below $2^{31}$), which is why the truncation issue doesn't effect it.

The other generator computes the function $$y\lfloor \tfrac{p}{a} \rfloor + z \mapsto az - (p\pmod{a}) y.$$ (The comparison to $0$ just ensures that the result is in $[0,p)$ without affecting the value modulo $p$.)

The idea is that $$a(y\lfloor \tfrac{p}{a} \rfloor + z) \equiv az + y(a\lfloor \tfrac{p}{a}\rfloor-p) \pmod{p}.$$ Now $a\lfloor\frac{p}{a}\rfloor-p = -(p\pmod{a})$, and so the other generator really computes $x \mapsto ax \pmod{p}$.

• the first modulo $2^{32}$ is probably the reason why the generator seems less efficient. Now, mathematically speaking, the generator with the rule $x_n = a\cdot x_{n-1} \pmod p$ has a period of $p-1$ (this is easy to prove, this is mostly because $a$ generates the multiplicative group $\mathbb{F}_p^{\times}$). The thing I want to understand is why with the formula $x_n = a \cdot \left(x_{n-1} \pmod{\frac{p}{a}}\right) - (p \pmod a) \cdot \left(x_{n-1} \cdot \frac{a}{p}\right)$ would generate the same group. – Laurent Hayez Oct 31 '14 at 18:51
• You should add a few floors to your formula: it's not $p/a$ but $\lfloor p/a \rfloor$, and it's not really $x_{n-1}\cdot\frac{a}{p}$ but rather $\lfloor x_{n-1}/\lfloor p/a \rfloor \rfloor$. – Yuval Filmus Oct 31 '14 at 19:06
• @Laurent I added an explanation. Your generator isn't "less efficient", it computes a different function. – Yuval Filmus Oct 31 '14 at 19:14