Generating random boolean values is a common challenge in programming tasks, especially when randomness is required for gaming or testing data.
With that said, let’s explore some methods to generate boolean values as quickly as possible.
Random Generators
In our previous discussion on the Random class in C#, covered in the article titled “Random Class in C#“, we explored some different random generators available in .NET. We identified two main types: the pseudo-random generator class, Random, and the cryptographically secure generator class, RandomNumberGenerator.
For most everyday programming tasks, we rely on the Random class. However, when dealing with security or cryptographic requirements, using the appropriate random generator, usually RandomNumberGenerator, is crucial. We have explored the RandomNumberGenerator in greater detail in our Create Cryptographic Numbers With RandomNumberGenerator article.
While cryptographically secure randomness might not be necessary in every scenario, it’s advisable to prioritize security whenever possible. However, it’s worth noting that RandomNumberGenerator tends to be significantly slower than the Random generator.
Random Classes for Our Testing Purposes
In .NET, random generators don’t offer a specific method for generating random boolean values. However, they do provide a general-purpose method for generating an array of various values, including booleans.
We’ll demonstrate creating bool values from int, long, double, byte, and boolean array. Let’s define the IRandomGenerator interface before proceeding:
public interface IRandomGenerator
{
int NextInteger(int fromInclusive, int toExclusive);
long NextLong(long fromInclusive, long toExclusive);
double NextDouble();
void GetItems<T>(ReadOnlySpan<T> choices, Span<T> destination);
}
This interface will encompass all the methods required for various algorithms to generate random boolean values.
Next, we need to create a concrete implementation of this interface. We do that using the RandomNumberGenerator and Random classes, and the implementation can be found by clicking on both links.
The results are clear and unmistakable:
| Method | NumberOfIntegers | Mean | |---------------------------- |----------------- |--------------:| | SystemRandomGenerator | 1000 | 2.017 us | | CryptographyRandomGenerator | 1000 | 46.283 us | | SystemRandomGenerator | 1000000 | 1,957.859 us | | CryptographyRandomGenerator | 1000000 | 45,801.955 us |
RandomNumberGenerator proves to be more than 20 times slower in heavy usage scenarios. Therefore, if cryptographic precision isn’t necessary for our task, it’s unsuitable for our purposes.
Generating Random Booleans
By measuring the speed of .NET built-in random generators, we’ve determined that the Random class offers the best performance in terms of speed.
Implementing the same interface is advantageous for consistency and ease of comparison. Different classes will implement different algorithms, but they will implement the same interface:
internal interface IBooleanGenerator
{
bool NextBool();
}
Generating a Random Boolean Using Integers
The concept is straightforward. We’ll generate an int, either 0 or 1, and if it’s 0, we’ll return true; otherwise, we’ll return false:
public class NextIntegerGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator
{
public bool NextBool() => randomGenerator.NextInteger(0, 2) == 0;
}
This implementation of the IBooleanGenerator interface takes one of the random generators we discussed earlier as a parameter.
The NextBool() method calls the underlying generator to produce an int, either 0 or 1, and from that, it constructs the bool value.
Generating a Random Boolean Using Doubles
We can apply a similar concept to floating-point numbers. The original generator always produces numbers between 0.0 and 1.0. Therefore, we can return true if the generated number is greater than 0.5:
public class NextDoubleGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator
{
public bool NextBool() => randomGenerator.NextDouble() > 0.5;
}
We are again implementing the IBooleanGenerator interface which accepts a random generator that implements the IRandomGenerator interface.
In this case, only the SystemRandomGenerator is suitable, as the CryptographyRandomGenerator does not implement the NextDouble() method.
Generating a Random Boolean Using GetItems
Our next method in the toolbox is the GetItems() method, capable of generating an array of various types of elements. Since it’s a generic method, it can also generate bool values:
public class GetItemsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator
{
public bool NextBool()
{
Span<bool> destination = stackalloc bool[1];
randomGenerator.GetItems([false, true], destination);
return destination[0];
}
}
The structure of the GetItemsGenerator class mirrors that of the previous NextDoubleGenerator and NextIntegerGenerator. However, this time, we utilize the GetItems() method.
The GetItems() accepts a ReadOnlySpan of possible values and then fills a Span with randomly selected items from it.
To generate bool values, we provide an array containing all possible boolean values [true, false], along with a destination Span with length 1. We use a stackalloc array to minimize memory allocations.Â
Base Benchmarking Methods
We will use the Random generator because it is faster than the RandomNumberGenerator generator. Also, we have prepared two helper methods for the benchmark, which you can find inside the BenchmarkBase.
The BenchmarkBase class will serve as the foundation for all our benchmarking activities.Â
We’ve implemented several algorithms and set up the foundational benchmarking methods. Now, it’s time to measure our initial results. We’ll test the creation of one thousand and one million random booleans using the SystemRandomGenerator and various algorithms:
| Method | NumberOfBooleans | Mean | Allocated | |--------------------- |----------------- |--------------:|----------:| | NextIntegerGenerator | 1000 | 6.387 us | 24 B | | NextDoubleGenerator | 1000 | 7.847 us | 24 B | | GetItemsGenerator | 1000 | 15.948 us | 24 B | | NextIntegerGenerator | 1000000 | 6,247.900 us | 72 B | | NextDoubleGenerator | 1000000 | 7,839.197 us | 120 B | | GetItemsGenerator | 1000000 | 15,467.424 us | 36 B |
The results of the NextIntegerGenerator and NextDoubleGenerator are pretty similar, but the performance of the GetItemsGenerator is notably worse.
This outcome is expected, considering that the GetItemsGenerator populates one million arrays with one boolean to create one million booleans, whereas the other generators accomplish this more directly.
Let’s investigate if using the GetItems() method for generating larger arrays at once makes any difference in performance.
GetItems() Method Can Already Generate an Array of Booleans
Let’s be fair in evaluating the performance of the GetItems() method by measuring how this benchmark compares with the others.
Instead of generating one million arrays with one boolean each, we’ll generate a single array with one million booleans. This approach will provide a more accurate representation of the GetItems() method’s performance. This time, we’ll need to store all the results since the GetItems() method returns the entire array, and the other methods must do the same.
Let’s compare the performance of this new method with the rest of them:
| Method | NumberOfBooleans | Mean | Allocated | |------------------------ |----------------- |----------------:|----------:| | GetItemsDirectGenerator | 1000 | 171.8 ns | 96 B | | NextIntegerGenerator | 1000 | 2,025.5 ns | 24 B | | NextDoubleGenerator | 1000 | 2,351.9 ns | 24 B | | GetItemsGenerator | 1000 | 10,895.0 ns | 24 B | | GetItemsDirectGenerator | 1000000 | 88,762.3 ns | 97 B | | NextIntegerGenerator | 1000000 | 1,980,366.4 ns | 26 B | | NextDoubleGenerator | 1000000 | 2,365,063.9 ns | 26 B | | GetItemsGenerator | 1000000 | 10,470,485.6 ns | 120 B |
This time, the direct call to the GetItems() method yields results similar to the NextIntegerGenerator.
However, it’s crucial to note that a direct call to GetItems() doesn’t respect our IBooleanGenerator interface. Our objective isn’t to generate an array of booleans at once but rather to have a method that can quickly generate a single boolean when needed.
GetItems() Method With Buffer
If we want to use this generator, we can significantly enhance its speed using the internal buffer. To make it respect our IBooleanGenerator interface, we can internally have a small buffer of booleans and replace it whenever we run out of new booleans:
public class GetItemsWithBufferGenerator(IRandomGenerator randomGenerator, int bufferLength) : IBooleanGenerator
{
private static readonly bool[] _allPossibilities = [false, true];
private readonly bool[] _buffer = new bool[bufferLength];
private int _currentBufferIndex = bufferLength;
public bool NextBool()
{
if (_currentBufferIndex >= _buffer.Length)
{
randomGenerator.GetItems<bool>(_allPossibilities, _buffer);
_currentBufferIndex = 0;
}
return _buffer[_currentBufferIndex++];
}
}
With that enhancement and the buffer of 128 elements, the code is still not as fast as a simple NextIntegerGenerator():
| Method | NumberOfBooleans | Mean | Allocated | |---------------------------- |----------------- |-------------:|----------:| | NextIntegerGenerator | 1000 | 6.416 us | 24 B | | GetItemsWithBufferGenerator | 1000 | 8.895 us | 192 B | | NextIntegerGenerator | 1000000 | 6,324.178 us | 72 B | | GetItemsWithBufferGenerator | 1000000 | 8,450.456 us | 288 B |
However, we can explore an alternative approach. We’ve observed that generating a single int, byte, double, or any other type is the primary bottleneck in our algorithms.
Generate a Random Bool Using a Single Bit
Currently, our fastest method involves translating the int result into a bool. However, we’re generating an integer on each iteration. But an int can have 4,294,967,296 different values! And we translate this into two values (true/false). This appears to be a significant waste of resources.
Since int in .NET is four bytes long, equivalent to 32 bits, and each bit can represent either zero or one (true or false), we can leverage this. We can direct the underlying random generator to produce an integer within the range from int.MinValue to int.MaxValue and then extract 32 random booleans from it.
Let’s test if this approach yields better performance:
public class NextIntegerBitsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator
{
private const int BitsInByte = 8;
private const int MaxBitIndex = sizeof(int) * BitsInByte;
private int _randomInteger;
private int _currentBufferIndex = MaxBitIndex;
public bool NextBool()
{
if (_currentBufferIndex >= MaxBitIndex)
{
_randomInteger = randomGenerator.NextInteger(int.MinValue, int.MaxValue);
_currentBufferIndex = 0;
}
return (_randomInteger & (1 << _currentBufferIndex++)) != 0;
}
}
We begin by determining the number of bits in a byte (BitsInByte) and the total number of bits in a single int (MaxBitIndex).
Next, we maintain two variables: _randomInteger to store the current random integer and _currentBufferIndex to track the current index we’re on while traversing the integer bits.
In the algorithm itself, we check the bit at the current index and return true if it’s set or false if it’s not set. If we exhaust all the bits in the int, we generate a new random int and reset the index to zero.
Now, the moment of truth: is this algorithm faster than the current fastest one? Let’s benchmark them:
| Method | NumberOfBooleans | Mean | Allocated | |------------------------- |----------------- |-------------:|----------:| | NextIntegerBitsGenerator | 1000 | 4.219 us | 32 B | | NextIntegerGenerator | 1000 | 6.428 us | 24 B | | NextIntegerBitsGenerator | 1000000 | 4,303.753 us | 35 B | | NextIntegerGenerator | 1000000 | 6,223.402 us | 72 B |
The results are clear: we have a new winner, NextIntegerBitsGenerator().
Bits Representation, Little Endian vs. Big Endian.
We might question whether this algorithm is correct when considering how int values are represented in computer memory. We know that there are two distinct representations of bytes in multibyte types in computers: Little Endian and Big Endian systems, each having a different approach to int representation. However, this is precisely why we want all possible negative and positive integers.
As all negative and positive integers together encompass any combination of bits across these bytes, we’re indifferent to which number these bits represent. We understand that all possible numbers will generate all possible combinations of bits.
To make this statement more straightforward, consider this: we don’t care if the combination of bits ‘0011’ represents the number 12 or 3.
However, it’s worth noting a slight inconsistency: the number int.MaxValue can never be generated; thus, this particular combination of bits will never occur. But remember, this is only one combination out of 4,294,967,296 possible combinations.
Generate a Random Boolean Using an Array of Bytes Instead of an Integer
As before, when we talked about GetItems() method, we can again find another method that we can use instead of NextInteger() and that is NextBytes() method. Similar to GetItems(), the method NextBytes() also returns an array of bytes, and we can then check the bits of each generated byte.Â
But again, measuring this approach shows that it is not faster than NextIntegerBitsGenerator().
From Integer to Long
Using the bits of an int is currently the fastest option. But we can use the long type as well to generate random bool values:
public class NextLongBitsGenerator(IRandomGenerator randomGenerator) : IBooleanGenerator
{
private const int BitsInByte = 8;
private const int MaxBitIndex = sizeof(long) * BitsInByte;
private long _randomLong;
private int _currentBufferIndex = MaxBitIndex;
public bool NextBool()
{
if (_currentBufferIndex >= MaxBitIndex)
{
_randomLong = randomGenerator.NextLong(long.MinValue, long.MaxValue);
_currentBufferIndex = 0;
}
return (_randomLong & (1L << _currentBufferIndex++)) != 0;
}
}
There is a very important detail here. When shifting bits, we have to use type long, and that is why there is a constant 1L and not just 1. Without this, if we use 1 we would shift an int instead of long, and the results would be wrong!
So, let’s check the result:
| Method | NumberOfBooleans | Mean | Ratio | Allocated | |------------------------- |----------------- |-------------:|------:|----------:| | NextLongBitsGenerator | 1000 | 4.064 us | 0.97 | 40 B | | NextIntegerBitsGenerator | 1000 | 4.199 us | 1.00 | 32 B | | | | | | | | NextLongBitsGenerator | 1000000 | 4,067.125 us | 0.99 | 43 B | | NextIntegerBitsGenerator | 1000000 | 4,101.540 us | 1.00 | 80 B |
If we are creating a lot of tests, sometimes one is faster, and sometimes the other is faster. These are pretty close.
Fairness of our Random Boolean Algorithms
Now that we have found the winner, it is also time to check if our algorithms are fair (producing consistently fair results).
Randomness is very tricky, and despite that it is unlikely, there is a possibility that if we throw a die ten times, we will get six at each throw. Even though this is theoretically possible, we would probably conclude that the die is unfair.
So, when generating ten million boolean values, we expect to generate around five million true values and five million false values. But why don’t we check:
Generator: true / False | From the middle
GetItemsGenerator: 4998654 / 5001346 | 0,0002692
NextDoubleGenerator: 5000626 / 4999374 | 0,0001252
NextIntegerGenerator: 4999618 / 5000382 | 0,0000764
NextIntegerBitsGenerator: 4996202 / 5003798 | 0,0007596
NextLongBitsGenerator: 5000193 / 4999807 | 0,0000386
By running this test many times, we see that all of our generators are fair and produce almost the same amount of random boolean values.
Conclusion
In this article, we’ve explored various algorithms for generating booleans. For a significant period, the most straightforward algorithm, which involves selecting integer numbers 0 as true and 1 as false, was the fastest option.
However, we’ve also discovered faster algorithms that leverage single bits for generating random boolean values, offering increased efficiency.
It’s safe to say that we can always rely on the simplest possible algorithm. However, if we desire or require a bit more speed, we can opt for manipulating bits and utilize the NextIntegerBitsGenerator or NextLongBitsGenerator algorithm.