2
$\begingroup$

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: Results, view 1

Results, view 2

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Oct 26 '14 at 20:10
  • $\begingroup$ Perhaps you could try to code both versions and see whether they agree. $\endgroup$ – Yuval Filmus Oct 26 '14 at 21:47
  • $\begingroup$ 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? $\endgroup$ – Laurent Hayez Oct 30 '14 at 19:42
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Oct 30 '14 at 20:01
  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 30 '14 at 19:57
1
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Laurent Hayez Oct 31 '14 at 18:51
  • $\begingroup$ 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$. $\endgroup$ – Yuval Filmus Oct 31 '14 at 19:06
  • $\begingroup$ @Laurent I added an explanation. Your generator isn't "less efficient", it computes a different function. $\endgroup$ – Yuval Filmus Oct 31 '14 at 19:14

Not the answer you're looking for? Browse other questions tagged or ask your own question.