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?
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?
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
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
A common problem in software performance is that you are essentially limited by memory access. Let us consider such a function where you write at random locations in a big array. for ( i = 0; i < N; i++) { // hash is a randomized hash function bigarray[hash(i)] = i; } This is a … Continue reading Speeding up a random-access function?
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
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?
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
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?
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
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)
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?
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)
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
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”
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
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
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
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+)
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