Testing 32bit vs 64bit PRNGs on a 32bit ESP32-C3 I'm seeing:

Very little difference on PRNGs that use 64bit operations vs 32bit operations. Even on limited hardware like this it makes sense to use a 64bit PRNG because you get more bytes per cycle.

Pseudo-random number generators use complex math to generate random numbers on your computer. These random numbers are used for all sorts of things: simulations, fractals, games, art, and even math experiments. Computers can only do math, which makes generating a random number difficult.

PRNGs need a "seed" number to kick off the math that generates sequences of random numbers. Some PRNGs require a 32bit seed, and some require a 64bit seed. Some PRNGs require one seed, and some require four (or more). It is important to know what type of seed your PRNG needs.

A 32bit number is between 0 and 4.2 billion and a 64bit number is between 0 and 18.4 quintillion. The larger a number is, the more bits are required to store it, and the better a seed it will make. The closer your seed is to the upper end of the number range the better. As a general rule a good seed will be a decimal number with 18 or 19 digits.

12 is a small number and not a good seed, 4611686018427387906 is a big number but still not a great seed. Seeds should not have large sections of zero/one bits. This is why small numbers do not make good seeds. Bits can be visualized by printing the number in binary:

# Horrible
$ perl -E 'printf("%064b\n", 4611686018427387906)'
0100000000000000000000000000000000000000000000000000000000000010

# Bad
$ perl -E 'printf("%064b\n", 17770)'
0000000000000000000000000000000000000000000000000100010101101010

# Poor
$ perl -E 'printf("%064b\n", 2850756010)'
0000000000000000000000000000000010101001111010110001010110101010

# Good
$ perl -E 'printf("%064b\n", 11337502976607798025)'
1001110101010110111001101110001101111000101001000100001100001001

Good seeds should have a roughly even mix of zero and one bits. 9223372036854775808 is a large number and looks promising but it has 63 zeros, and only a single one bit. You can visualize the quality of your seed with seed_quality.pl. Quality above 75% should make for good seed numbers.

Seeds should not be predictable. Do not use dates, times, or phone numbers as they are potentially guessable. Combinations of numbers can be good sources. Process PID, UID, unixtime are good potential sources if they are combined together in a non-predictable way. PID multiplied by UID multiplied by Unixtime is an example of combining values. Memory locations of variables, especially if ASLR is in use is a potentially good source as well.

Hashing numbers, strings, or combinations of numbers can be a good way to generate seeds. Hashing a value with Komihash or xxHash will generate a suitable 64bit number. Hashing a value with SHA256 will generate a 256bit value which can be split into four 64bit values. Hashing functions also do a good job of ensuring the bits are mixed well and do not include large repeating sections.

The best source of seed numbers is directly from your OS. On Linux this is /dev/urandom and on Windows you can interface with the RtlGenRandom API. These are carefully curated sources of true randomness, but they can be slow-ish. Using them as a source for a fast PRNG is best practice.

sub get_64bit_seed {
    open my $urandom, '<:raw', '/dev/urandom' or croak("Couldn't open /dev/urandom: $!");
    sysread($urandom, my $buf, 8) or croak("Couldn't read from csprng: $!");

    return unpack("Q*", $buf);
}

I'm a big fan of the PCG32 PRNG. It's simple, fast, and well documented. As is usually the case when I find interesting code I try and find a way to implement it in Perl. PCG32 poses an interesting problem when one tries to implement it in Perl because all the math is performed using unsigned integers and overflow. Most PRNGs use large numbers and overflow to work, that's their secret sauce.

Perl does not have a native unsigned type so I had to learn the guts of how Perl does math so I could emulate it. I ended up coming up with two different implementations, a native Perl implementation, and a version that uses Math::Int64. Surprisingly the native version was significantly faster.

Both implementations with detailed comments are available in pcg32.pl if you're interested in learning more about how to do integer style math in Perl.

As a bonus I also ported the xoshiro256 family into Perl. Splitmix64 ended up being a little more complicated to port, but I got it as well.

I need a simple way to hash strings into 64bit integers so I started some research. Initially I was focusing on xxHash but it's slightly complicated to implement. I ended up landing on the amazing Komihash which bills itself as: "a very fast 64-bit hash function, mainly designed for hash-table, hash-map, and bloom-filter uses".

Komihash is available as a single Komihash.h file and is extremely easy to implement into existing code.

#include <stdio.h>
#include <stdlib.h>
#include "komihash.h"

int main(int argc, char *argv[]) {
    int seed        = 0;
    const char *buf = "Hello world";

    uint64_t hash_num = komihash(buf, strlen(buf), seed);

    printf("Komihash: %s = %llu\n", buf, hash_num); // 3745467240760726046
}

As a bonus it also comes with a PRNG which is equally simple to implement:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "komihash.h"

int main(int argc, char *argv[]) {
    uint64_t seed1 = time(NULL) * 0x61c8864680b583ebull; // hash64
    uint64_t seed2 = seed1      * 0x61c8864680b583ebull; // hash64

    for (int i = 0; i < 5; i++) {
        uint64_t rand64 = komirand(&seed1, &seed2);
        printf("Komirand: %llu\n", rand64);
    }
}

In fact, I liked it so much I ported it to Perl and called it Crypt::Komihash.