True Random Numbers - Computerphile

Source: True Random Numbers - Computerphile, Computerphile, 12:15, uploaded 2023-11-09, category Computer Science / AI, playlist index 1303.

Dr Valerio Giuffrida starts with the random-number function that appears somewhere in almost every coding project. The function usually returns a pseudo-random sequence. It looks random enough for many tasks, although the computer follows a fixed algorithm from a starting state. The video then moves from software to the processor itself and asks whether hardware can supply a number that the program could not have predicted in advance.

Seeds, sequences, and useful repetition

Most pseudo-random number generators begin with a seed. The seed sets the generator’s initial state. Each call applies the same operations to the current state, returns a number, and leaves a new state for the next call. The sequence therefore depends on the first state and the algorithm. Running the program again with the same seed produces the same sequence.

The statistical behaviour can resemble a fair die. A good generator gives each possible result a controlled probability, so a long sequence has properties that make it useful for simulations and ordinary program logic. The numbers remain algorithmic, though. A program can reproduce the whole sequence when it knows the seed and the generator.

That repeatability helps when a random-looking program fails. A bug might depend on one particular value appearing at one point in an execution. A fixed seed lets the programmer reach the same sequence again, so the failure can be inspected without waiting for the same accident to occur.

Randomness from the processor

Software follows its own instructions, so a software algorithm cannot create an event outside that chain of instructions. Hardware can provide an input that the algorithm did not determine. Giuffrida says that dedicated devices can do this, and that many relatively recent Intel and AMD x86 processors include the necessary circuitry themselves.

The x86 instruction set exposes two relevant instructions, RDRAND and RDSEED. Giuffrida describes RDRAND as drawing from a pseudo-random generator inside the processor. He presents RDSEED as the route to a value from the processor’s hardware entropy source. The distinction gives the video its practical answer: a true random value can enter a deterministic program as an initial state.

The example uses C. A function called get_true_random_number receives a pointer where it can store the result and returns a status value. The x86 intrinsic _rdrand32_step looks like an ordinary C function in the source code, although the compiler treats it specially and emits the matching assembly instruction. The function returns 1 when the instruction succeeds and 0 when it fails.

The code depends on x86. Giuffrida warns that the example will not work on a Raspberry Pi, whose processor uses the ARM instruction set. Other languages can wrap the same processor feature, although the video keeps the demonstration in C so the compiler output stays visible.

The processor’s separate clock

The random-number circuitry has its own timing. Giuffrida cites Intel’s documentation for an 800 MHz clock that runs independently of the computer’s main processor clock. When the processor requests a value, the random unit may need time to make one available. The requesting code can wait, or the processor can continue and report a failure when the value is unavailable at that moment.

That failure does not mean that the instruction has returned a bad number. It means that the caller has to try again. Giuffrida compiles the example with GCC’s -mrdrnd flag so the required intrinsic is enabled, then uses -O3 to keep the generated assembly short. In Compiler Explorer, also called Godbolt, the result contains the RDRAND instruction and places its output in a CPU register before the surrounding code handles it.

The demonstration asks for 1,000 values. The processor returns them without a visible failure in the run shown. Giuffrida says Intel recommends retrying the instruction up to ten times because a busy processor can exhaust the immediately available values. Ten consecutive failures should be rare, although repeated failures could point to a processor problem. That guidance comes from the video and its reference to Intel documentation; the episode does not test failure rates across different processors.

Why direct hardware output has limited use

The direct call has two drawbacks. It is slower than a software generator, and Giuffrida says it carries no statistical guarantee about the distribution of the values it returns. A result could repeat several times, favour a particular range, or show some other skew. The processor’s entropy source remains hidden from the program, so the caller cannot inspect the process that produced the bits.

A pseudo-random generator supplies a designed distribution. It can make every value in its intended range equally likely, subject to the generator and the way the program uses its output. The hardware instruction supplies an unpredictable input while leaving those distribution properties to chance. That makes a true random value a poor replacement for every ordinary call to a pseudo-random function.

A true seed for a fast sequence

The useful arrangement combines both kinds of generator. The C example calls RDSEED to obtain one hardware-generated value, passes that value to srand, and then asks the ordinary C generator for 1,000 numbers. Running the program again produces a different initial seed, so the later sequence changes as well. After the seed arrives, the program uses the fast deterministic path.

This gives each part a defined job. Hardware supplies an unpredictable starting point. Software expands that point into a long sequence with the speed and statistical behaviour expected by the rest of the program. The source’s title asks whether computers can generate true random numbers. Its answer is narrower and more useful: the processor can supply entropy, while the program still needs a pseudo-random generator to turn that entropy into a practical stream.

The captions contain recognition errors around the instruction names and C identifiers. I have normalised RDRAND, RDSEED, _rdrand32_step, srand, and Compiler Explorer from the surrounding explanation and the code terms that the captions attempt to transcribe. The note preserves Giuffrida’s account of the processor’s guarantees and failure behaviour. It does not treat the video’s description of the hardware entropy source as an independent test of Intel or AMD implementations.

Further reading / references

• Compiler Explorer, the compiler and assembly viewer used in the demonstration.