Random Number Generator

Random Number Generator (RNG)

Discovered independantly by Roadrunnerwmc and lepelog

Skyward Sword uses a modified version of the linear congruential pseudo-random number generator (PRNG) known as ranqd1 (qd for quick and dirty). The upside of this generator is that it is very fast, and it is also known to normally always have a full period of 2^32 states. It contains a single variable, called the rng seed. Everytime it is called, its value changes according to the following equation:

Or in pseudocode:

function ranqd1(seed: u32):
    temp: u64 <- 1664525 * (seed as u64) + 1013904223
    seed <- temp mod (2**32)                                            # keeping only the lowest 32 bits
    return seed

This is also the RNG used for Twilight Princess. However, Nintendo changed something from the classic generator for Skyward Sword. It now performs one extra step: they decided to add up the lower 32-bits and upper 32-bits of the seed value together, and return that instead. They are basically trying to "recycle" the upper 32 bits which are normally discarded. It looks like this in pseudocode:

function ranqd1_modified(seed: u32):
    temp: u64 <- 1664525 * (seed as u64) + 1013904223
    temp <- lower_32_bits(temp) + upper_32_bits(temp)
    seed <- temp mod (2**32)                                             # keeping only the lowest 32 bits
    return seed

This fundamentally changes the mathematical properties of the generator. Due to this, the rng seed will always loop much more quickly to the same values than a good pseudo-random number generator would ever do. There are 1653 possible loop. The biggest possible loop has a cycle of length 1 708 724, which corresponds to about 75% of possible values. The possible loops and their cycles are seen below:

Length of Loop	Number of Loops
1 708 724	1
354 835	1
155 834	1
146 318	1
127 646	1
81 673	1
48 534	1
26 128	1
1371	1
8	1630
4	12
2	1
1	1

Interestingly, there now exists a single cycle of length 1, that happens if the rng seed is initialized to value 1 144 735 523, which means our function has a fixed point. We can do the maths to showcase why this is the case:

The first step is to apply the equation: 1 664 525 * 1 144 735 523 + 1 013 904 223 = 1 905 441 910 325 798.

As a 64-bit integer, 1 905 441 910 325 798 is represented as 0x0006C4FD44348226 in hexadecimal.

We now add up the upper and lower 32 bits together: 0x0006C4FD + 0x44348226 = 0x443B4723.

In decimal representation, this new number corresponds to 1 144 735 523, which is exactly the number we started with. It is thus, while unbelievably unlikely, possible to boot up the game and have the rng locked to this single value. If this were to happen, many things would look very odd, such as grass spawning in a perfect pattern, or some enemies stuck never or always attacking. There are 4 other initial values that could also lead to this fixed point: 285 742 064, 2 003 728 982, 2 862 722 441, and 3 721 715 900.