2
$\begingroup$

I found note about XSL-RR-RR on wikipedia:

https://en.wikipedia.org/wiki/Permuted_congruential_generator

But I don't understand what this means:

  1. count = (int)(x >> 122)
  2. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)
  3. high64 = rotr((uint64_t)(x >> 64), low64 & 63)
  4. return (uint128_t)high64 << 64 | low64

What is difference between rotr and rotr64? What is "int"? Is rotr64((uint64_t)(x ^ (x >> 64)), count) doing rotr64 by count steps (am I understand it right)? What is "|"? And what is "uint64_t"? At least I understand "^", "&" and ">>".

Is XSL-RR-RR eliminate low bits periods known from typical LCG? As I understand that's why it was invented.

$\endgroup$
3
  • 1
    $\begingroup$ Code is here pcg-random.org and see iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf and pcg-random.org/pdf/hmc-cs-2014-0905.pdf $\endgroup$
    – kelalaka
    Jan 1 at 23:03
  • $\begingroup$ My problem was the most with code. I don't know C. After all there is not much about XSL-RR-RR in original paper. But after few hours I think I understand what is going on. What's more there is probably a mistake in high64. There could be rotr64 istead of rotr (if it make a difference). $\endgroup$
    – Tom
    Jan 2 at 22:13
  • 1
    $\begingroup$ Good, you can post your answer when you find answers to your questions, and update the Wikipedia, too, Yes, The paper doesn't include much about it, that is why I've provided you the code. Make sure that you write XSL-RR-RR very clean so that other cannot have struggle like you. regs. $\endgroup$
    – kelalaka
    Jan 2 at 22:19
2
$\begingroup$

I have read a bit about C syntax and I seem to understand what this generator does.

  1. count = (int)(x >> 122)

>> is the right bitshift operator, shifting all the bits to the right a specified number. So initial number $x$ is shifted by $122$ bits. It means count is number consist of first $6$ most signifficant bits of $x$. Type of this data is int, because it could be every $0$-bit, $1$-bit, $2$-bit, $4$-bit, $5$-bit, $6$-bit number.

  1. low64 = rotr64((uint64_t)(x ^ (x >> 64)), count)

^ is just XOR operation. After xoring we can get every $128$-bit number, that's why there is introduced type uint64_t. It means we have to cut our result to first $64$ least signifficant bits. Rotr64 rotates the bits $x$ to the right by $n$ places around a $64$-bit boundary, which means we rotate (uint64_t)(x ^ (x >> 64) by count places.

  1. high64 = rotr64((uint64_t)(x >> 64), low64 & 63)

Here we have the same operations like above except & which is the logical AND operator.

  1. return (uint128_t)high64 << 64 | low64

In the end we get $128$-bit number (uint128_t). high64 bits are shifting on most signifficant bits positions and | is the logical OR operator. All $64$ least signifficant bits after << 64 will be equal to $0$. So OR operator just copy all $1$ and $0$ of low64 to $64$ least signifficant bits in our final $128$-bit number.

And $x$ is just number taken from typical linear congruential generator modulo $2^{n}$. Author specified in the documentation two multipliers and increments, which we can use:

$m=2549297995355413924$, $i=4865540595714422341$

and

$m=6364136223846793005$, $i=1442695040888963407$

$\endgroup$

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.