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$

closed as unclear what you're asking by D.W., David Richerby, Rick Decker, Luke Mathieson, Juho Dec 1 '14 at 10:31

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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