Are 64-bit random identifiers free from collision?

It is common in software system to map objects to unique identifiers. For example, you might map all web pages on the Internet to a unique identifier. Often, these identifiers are integers. For example, many people like to use 64-bit integers. If you assign two 64-bit integers at random to distinct objects, the probability of … Continue reading Are 64-bit random identifiers free from collision?

A fast 16-bit random number generator?

In software, we often need to generate random numbers. Commonly, we use pseudo-random number generators. A simple generator is wyhash. It is a multiplication followed by an XOR: uint64_t wyhash64_x; uint64_t wyhash64() { wyhash64_x += 0x60bee2bee120fc15; __uint128_t tmp; tmp = (__uint128_t) wyhash64_x * 0xa3b195354a39b70d; uint64_t m1 = (tmp >> 64) ^ tmp; tmp = (__uint128_t)m1 … Continue reading A fast 16-bit random number generator?

Nearly Divisionless Random Integer Generation On Various Systems

It is common in software to need random integers within a range of values. For example, you may need to pick an object at random in an array. Random shuffling algorithms require such random integers. Typically, you generate a regular integers (say a 64-bit integer). From these integers, you find a way to get integers … Continue reading Nearly Divisionless Random Integer Generation On Various Systems

Almost picking N distinct numbers at random

In Picking N distinct numbers at random: how to do it fast?, I describe how to quickly pick N distinct integer values are random from a range of integer values. It comes down to using either bitset/bitmap or a hash set. The bitset approach is very fast when you need to pick many integer values … Continue reading Almost picking N distinct numbers at random

ARM and Intel have different performance characteristics: a case study in random number generation

In my previous post, I reviewed a new fast random number generator called wyhash. I commented that I expected it to do well on x64 processors (Intel and AMD), but not so well on ARM processors. Let us review again wyhash: uint64_t wyhash64_x; uint64_t wyhash64() { wyhash64_x += 0x60bee2bee120fc15; __uint128_t tmp; tmp = (__uint128_t) wyhash64_x … Continue reading ARM and Intel have different performance characteristics: a case study in random number generation

The fastest conventional random number generator that can pass Big Crush?

In software, we sometimes want to generate (pseudo-)random numbers. The general strategy is to have a state (e.g., a 64-bit integer) and modify it each time we want a new random number. From this state, we can derive a “random number”. How do you that you have generated something that can pass as a random … Continue reading The fastest conventional random number generator that can pass Big Crush?

Fast Bounded Random Numbers on GPUs

We often use random numbers in software in applications such as simulations or machine learning. Fast random number generators tend to produce integers in [0,232) or [0,264). Yet many applications require integers in a given interval, say the interval {0,1,2,3,4,5,6,7}. Thus standard libraries frequently provide a way to request an integer within a range. How … Continue reading Fast Bounded Random Numbers on GPUs

Are vectorized random number generators actually useful?

Our processors benefit from “SIMD” instructions. These instructions can operate on several values at once, thus greatly accelerating some algorithms. Earlier, I reported that you can multiply the speed of common (fast) random number generators such as PCG and xorshift128+ by a factor of three or four by vectorizing them using SIMD instructions. A reader … Continue reading Are vectorized random number generators actually useful?

Predicting the truncated xorshift32* random number generator

Software programmers need random number generators. For this purpose, the often use functions with outputs that appear random. Gerstmann has a nice post about Better C++ Pseudo Random Number Generator. He investigates the following generator: uint32_t xorshift(uint64_t *m_seed) { uint64_t result = *m_seed * 0xd989bcacc137dcd5ull; *m_seed ^= *m_seed >> 11; *m_seed ^= *m_seed << 31; … Continue reading Predicting the truncated xorshift32* random number generator

Vectorizing random number generators for greater speed: PCG and xorshift128+ (AVX-512 edition)

Most people designing random number generators program using regular code. If they are aiming for speed, they probably write functions in C. However, our processors have fast “vectorized” (or SIMD) instructions that can allow you to go faster. These instructions do several operations at once. For example, recent Skylake-X processors from Intel can do eight … Continue reading Vectorizing random number generators for greater speed: PCG and xorshift128+ (AVX-512 edition)

When shuffling large arrays, how much time can be attributed to random number generation?

It is well known that contemporary computers don’t like to randomly access data in an unpredictible manner in memory. However, not all forms of random accesses are equally harmful. To randomly shuffle an array, the textbook algorithm, often attributed to Knuth, is simple enough: void swap(int[] arr, int i, int j) { int tmp = … Continue reading When shuffling large arrays, how much time can be attributed to random number generation?

Picking distinct numbers at random: benchmarking a brilliant algorithm (JavaScript edition)

Suppose you want to choose m distinct integers at random within some interval ([0,n)). How would you do it quickly? I have a blog post on this topic dating back to 2013. This week I came across Adrian Colyer’s article where he presents a very elegant algorithm to solve this problem, attributed to Floyd by … Continue reading Picking distinct numbers at random: benchmarking a brilliant algorithm (JavaScript edition)

Benchmarking algorithms to visit all values in an array in random order

In an earlier post, I described how to visit all values in an array in a pseudo-random order quite fast. The idea is simple, given an array of size n, pick a value a that is coprime with n. Then for any value of b, you have that (a x + b ) modulo n … Continue reading Benchmarking algorithms to visit all values in an array in random order

Visiting all values in an array exactly once in “random order”

Suppose that you want to visit all values in an array exactly once in “random order”. You could do it by shuffling your array but it requires some extra storage. You want your code to use just a tiny bit of memory, and you want the code to be super fast. You do not want … Continue reading Visiting all values in an array exactly once in “random order”

The Xorshift1024* random number generator fails BigCrush

In software, we use random number generators to simulate randomness. They take the form of functions which return numbers that appear random. To test their quality, we apply statistical tests. The goal standard is a statical test called BigCrush. It tests that quality of 32-bit random values. In an earlier post, I reported that contrary … Continue reading The Xorshift1024* random number generator fails BigCrush

The Xorshift128+ random number generator fails BigCrush

In software, we generate randomness with algorithms called “pseudo-random number generator”, sometimes simply called “random number generator” or RNG. A popular random number generator is xorshift128+: it is used by many JavaScript engines. It was designed by an influential computer science professor, Sebastiano Vigna, who has done a lot of great work. I suspect that … Continue reading The Xorshift128+ random number generator fails BigCrush

Testing non-cryptographic random number generators: my results

In software, we use random number generators to emulate “randomness” in games, simulations, probabilistic algorithms and so on. There are many definitions of what it means to be random, but in practice, what we do is run statistical tests on the output of the random number generators. These tests are not perfect, because even a … Continue reading Testing non-cryptographic random number generators: my results

“Cracking” random number generators (xoroshiro128+)

In software, we generate random numbers by calling a function called a “random number generator”. Such functions have hidden states, so that repeated calls to the function generate new numbers that appear random. If you know this state, you can predict all future outcomes of the random number generators. O’Neill, a professor at Harvey Mudd … Continue reading “Cracking” random number generators (xoroshiro128+)

On Melissa O’Neill’s PCG random number generator

Computers often need random numbers. Most times, random numbers are not actually random… in the sense that they are the output of a mathematical function that is purely deterministic. And it is not even entirely clear what “really random” would mean. It is not clear that we live in a randomized universe… it seems more … Continue reading On Melissa O’Neill’s PCG random number generator