Pseudo-random number generator port from C

Question

C code:

uint32_t pcg32_random_r(pcg32_random_t* rng)
{
 uint64_t oldstate = rng->state;
 rng->state = oldstate * 6364136223846793005ULL + rng->inc;
 uint32_t xorshifted = ((oldstate >> 18u) ^ oldstate) >> 27u;
 uint32_t rot = oldstate >> 59u;
 return (xorshifted >> rot) | (xorshifted << ((-rot) & 31));
}

Attempted Java port (slightly fixed from GitHub):

public int nextInt() {
 long oldState = state;
 state = oldState * MULTIPLIER + inc;
 int xorShifted = (int) (((oldState >>> 18) ^ oldState) >>> 27);
 int rot = (int) (oldState >>> 59);
 return Integer.rotateRight(xorShifted, rot);
}

Are there differences in behavior? * and + should give the same bitwise results for signed arithmetic in Java and unsigned in C++, >>> in Java is the same as >> in C... But am I missing something?

• rolfl: Have you tested the code? If you run both of the code segments they should produce the same sequence with the same seeds. Does it?
• Alexey Romanov: Yes, I did check with a few seeds. This doesn't mean there are no edge cases where they are different. In particular I worry that C might be inserting conversions at different places than I did and they happen to produce the same result in the places I've tried.
• Alexey Romanov: (As said, I've already found one mistake in my original port, so there might be subtler ones as well.)

Answer 1

I cannot see any functional issues when comparing the C code against the Java code. it would seem they should produce the same results given the same input. Of course, a logical course of action would be to write a test system for the code which wraps the C code in to a program which accepts a single seed value as an argument, and produces a stream of int values in 'network byte' order. You then pipe that stream in to a Java program which produces the same stream, and compares the results. I would actually set up a test where the Java program starts a sub-process for the C version, and runs it with many input seeds, including the logical edge-cases (0, 1, -1, Long.MAX_VALUE, Long.MinValue, and all seeds from -100 to +1000). For each run, compare the first 10,000 generated values.

That would give me some measure of confidence that the code is a faithful reproduction.

Like you, I believe the Java code is a fair reproduction, but, like you, I would want to check it again.

Now,about the code, you are doing unnecessary work. There is no need to store the oldState:

public int nextInt() {
 long oldState = state;
 state = oldState * MULTIPLIER + inc;
 int xorShifted = (int) (((oldState >>> 18) ^ oldState) >>> 27);
 int rot = (int) (oldState >>> 59);
 return Integer.rotateRight(xorShifted, rot);
}

That code can be reduced to:

public int nextInt() {
 int xorShifted = (int) (((state >>> 18) ^ state) >>> 27);
 int rot = (int) (state >>> 59);
 state = state * MULTIPLIER + inc;
 return Integer.rotateRight(xorShifted, rot);
}

Also, while your comments about the >>> vs >> are accurate, and I prefer the use of >>> here, you should also know that the only shift which has a significant impact (where using >>> makes a difference vs. >>) is the part:

(state >>> 18)

In that shift, if it was a negative state, and you used >>, it would shift the sign bit to position 46 (and all higher bits). Then the subsequent >>> 27 would shift those effects in to the low-order 32-bits. Since the value is truncated to 32 bits, any sign-shift effects which happen above 32 bits are irrelevant, and as I say, the only sign-shift which can effect the low 32 bits is the first one.

Also, Java uses a mask on the int rotate value, and for Integer.rotateRight it only considers the low-5 bits in the value, so the following are identical because the rotate effectively applies the mask 0x1f to the value anyway:

Integer.rotateRight(xorShifted, (int)(oldState >>> 59))
Integer.rotateRight(xorShifted, (int)(oldState >> 59))

You may want to test the performance of each, and exercise your profiler....

• Alexey Romanov: The idea behind storing oldState is that this version has instruction-level parallelism between calculating new state and xorShifted. JVM should be able to take advantage of this just like C compilers. Good idea about starting C as a process for testing, I'll do that.
• rolfl: @AlexeyRomanov - in my testing, there is essentially no performance difference between having the oldState, and not.