2
\$\begingroup\$

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?

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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