Pseudo-random number generator port from C

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?

• 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? Mar 4 '15 at 12:20
• 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. Mar 4 '15 at 12:48
• (As said, I've already found one mistake in my original port, so there might be subtler ones as well.) Mar 4 '15 at 12:56

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

• 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. Mar 4 '15 at 16:30
• @AlexeyRomanov - in my testing, there is essentially no performance difference between having the oldState, and not. Mar 4 '15 at 16:54