Computers cannot generate (or very difficult) true random numbers. In practise, psudo-random generators are used. To avoid ‘patterns’ for generated ‘random’ numbers, a seed is often used to re-arrange the sequence. For example,
1 2 3 4 5 6 7 8 | #include <stdlib.h> #include <time.h> int main() { srand (time(NULL)); // seed cout << rand() << endl; // print a random number between 0 and RAND_MAX return 0; } |
#include <stdlib.h> #include <time.h> int main() { srand (time(NULL)); // seed cout << rand() << endl; // print a random number between 0 and RAND_MAX return 0; }
Modern random generators/algorithms are already good enough to ensure a high level of randomness. However, they might be slow. In case you want to generate random numbers a million times (for instance, at innermost loops), the performance of entire application depends heavily on such random generators.
XorShift should be another options that can be quite good to consider. The XorShift is developed by George Marsagli and it is a random generator that executes faster and uses less space. Its principle is based on binary XOR shift which is invertible.
The parameters have to be carefully chosen in order to achieve a longer period (sequence) of the random numbers. The following XORShift has a period of
1 2 3 4 5 6 7 8 9 10 | uint32_t xor128(void) { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } |
uint32_t xor128(void) { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); }
Obviously, this is extremely fast by only using integer operations (shift, or etc). But how do we know it truly generates ‘random’ numbers like the ‘rand()’ we use a lot as well?
We can generate a bmp picture and see easily if it has any pattern. If no clear pattern is observed, then it is a good-enough random generator.
For C++ to write a BMP file fast, we can use C++ BMP Library
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include "bitmap_image.hpp" using namespace std; uint32_t xor128(void) { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } int main() { bitmap_image image(500, 500); image_drawer draw(image); const unsigned int width = image.width(); const unsigned int height = image.height(); for (std::size_t y = 0; y < height; ++y) { for (std::size_t x = 0; x < width; ++x) { color = xor128(); // random image.set_pixel(x, y, color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF); } } image.save_image("output.bmp"); return 0; } |
#include "bitmap_image.hpp" using namespace std; uint32_t xor128(void) { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = w ^ (w >> 19) ^ (t ^ (t >> 8)); } int main() { bitmap_image image(500, 500); image_drawer draw(image); const unsigned int width = image.width(); const unsigned int height = image.height(); for (std::size_t y = 0; y < height; ++y) { for (std::size_t x = 0; x < width; ++x) { color = xor128(); // random image.set_pixel(x, y, color & 0xFF, (color >> 8) & 0xFF, (color >> 16) & 0xFF); } } image.save_image("output.bmp"); return 0; }
and well, the above C++ code produces a random picture (below compressed and resized a little bit) base on such fast random generator XorShift
No clear pattern can be observed by the following BMP, thus XorShift achieves a high level of randomness and can be executed in a short amount of time on modern computing architectures.
Reference:
[1] http://en.wikipedia.org/wiki/Xorshift
–EOF (Coding For Speed) —
Product Recommendations
- Make Your WordPress Fast Again! This WordPress is accelerated by WP Rocket Plugin!
- Free $10 Credit, when you sign up with Vultr Cloud VPS (4 Months Giveaway!)
- Free $10 Credit, when you sign up with Digital Ocean Cloud VPS (2 Months Giveaway!)
- Free $20 Credit, when you sign up with Linode Cloud VPS (4 Months Giveaway!) - (Coupon: PodCastInit2022)
- The easiest way to Buy and Sell Bitcoins/Litecoins via Wirex Visa Debit Card!
- Buy and Sell Bitcoins/Litecoins via Local Bitcoins