All posts tagged "random"

  • Non-binary Linear Feedback Shift Registers

    There’s way too much documentation about binary LFSRs out there, and not a whole lot on doing the same with other bases. So I’ve put together some tables and a few notes so everybody can throw something together without to much effort.

  • A reasonably effective hash instruction

    As per part one of this post, I have reasoned through and tested a proof of concept for generic CPU instruction which could achieve most of the required mixing of a good hash function in a single cycle (working with a combinational depth of 20 to 24 gates as a guide).

  • Why I want a dedicated hash instruction

    A good hash function is expected to remove correlations of various sorts between subsets of inputs and their hashed outputs in order to mitigate the risk of those correlations producing performance aberrations (cache collisions, unbalanced structures, etc.) or statistical biases.

  • N-bit Mixer Functions

    For reasons I intend (hah!) to go into in a longer post I was looking for operations with which to construct and whiten (or “finalise” or “mix” or “avalanche” or whatever) RNGs with 2n periods. I was looking at splitmix64 which led me to Fast splittable pseudorandom number generators which cited Improving on MurmurHash3’s 64-bit Finalizer (although I found that page by other means) and finally MurmurHash3 which tells me where those constants and that construction both come from.

  • Minimally biased NPOT-ranged random numbers

    In my previous post I described a technique for scaling random numbers to new intervals producing extremely small bias but with a constant execution time.

  • Random number scaling

    I’ve been doing some messing around with random number generation at work, and this inspired me to revisit something which has troubled me since my teenage years: Perfectly unbiased random numbers over a range which is not a power of two.