Daniel Lemire's blog

, 5 min read

Programming competition with $1000 in prizes: make my code readable!

7 thoughts on “Programming competition with $1000 in prizes: make my code readable!”

  1. Alun J. Carr says:

    A pity that the contest is not directed at PCG:


    However, since the C code is so simple, I’m not sure that it can be further simplified.

    1. My impression is that there is no rule against PCG.

    2. Travis Downs says:

      As far as I can tell, PCG and the algorithm the contest is about are orthogonal or even complementary: the former is a way of creating uniform random bits, and the latter is a way Daniel proposes of taking random bits and creating an uniform integer within a given range.

      So you can use PCG, or any other bit-producing RNG to feed Daniel’s algorithm.

  2. MyName says:

    Where should the contribution be submitted?

    1. I suggest reaching out to Colm on Twitter.

  3. anon says:

    You’ll be glad to hear that julialang is also in the process to migrating to your algorithm (PR here), with proper attribution. I’m not rfourquet, so I don’t know whether you accept my nomination on his behalf.

    On a different note, we recently adopted a similar strategy for unpacking bit-arrays to the one you propagate on your blog (we arrived on the same solution independently of you, as countless of others before either of us). This is used for matlab-style logical indexing (PR here).

  4. KWillets says:

    I was looking at this over the weekend, and I’m not sure if my ideas would make the code more, or less readable.

    The 64-bit multiplication and 32-bit extractions are really just fixed-point arithmetic, and I was looking at rewriting this with some kind of fixed point library, but I didn’t find anything convenient.

    I did come up with the idea of saving (-range % range) between calls with some kind of RangeGenerator object. That’s not much use in shuffling, but it may be in other contexts.

    Another tricky part is compile time vs. runtime optimization, since eg the modulus could be computed at compile time in the case of a constant range. The runtime version should be lazy-evaluated, but compile time should not.