Skip to content
Tutorials Center
My learning

Topics

Lesson 92 of 132 ยท Standard Library Tour

Randomness, Hashing and Math

Write seeded random generators (LCG, xorshift, PCG) by hand, shuffle fairly, use Hash and Hasher with a custom FNV hasher, and master f64 math, isqrt and gcd in Rust.

Three topics that look unrelated share one idea: turning numbers into other numbers in a way that looks unpredictable or compact. Random number generators turn a seed into a stream of numbers. Hash functions turn arbitrary data into a fixed-size number. Math functions turn numbers into numbers following the rules of arithmetic, with the quirks of floating point. This lesson covers all three using only the standard library.

One surprise first: Rust's standard library has no random number generator. Random numbers live in the rand crate. That is a deliberate choice: the standard library stays small, and good randomness has many trade-offs (speed, statistical quality, security) that a crate can evolve faster than the language. Since our editor has no crates, we will write tiny generators ourselves. This is also a great way to learn wrapping arithmetic and bit operations.

Every generator in this lesson is not cryptographically secure. Never use them for passwords, tokens, session IDs or anything an attacker must not guess. In real programs use the rand crate (its thread_rng/rng is seeded from the operating system) or the getrandom crate for secrets.

Pseudo-random numbers: seeds and state

A pseudo-random number generator (PRNG) is a tiny machine with some internal state. Each time you ask for a number it updates the state with a fixed formula and returns something derived from it. Given the same starting state (the seed), it always produces the same sequence. That sounds like a flaw but it is a feature: simulations, games and tests become reproducible. A bug found with seed 42 can be replayed forever.

The oldest simple design is the linear congruential generator (LCG):

TEXT
state = state * a + c   (mod 2^64)

In Rust, "mod 2^64" is exactly what wrapping_mul and wrapping_add on u64 do. Normal * would panic on overflow in a debug build, so wrapping operations are essential here.

Rust A seeded LCG

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Because the seed fully determines the output, the printed numbers are the same on every run and on every machine. The "random" part is only that they look unpredictable.

LCGs are easy to write but weak: their low bits repeat with short periods (the lowest bit simply alternates), which is why we take the high 32 bits. Better generators scramble the output before returning it.

Better generators: xorshift and PCG

Xorshift generators mix the state with shifts and XORs, with no multiplication in the state update, and are fast. PCG (permuted congruential generator) keeps an LCG as the state but applies a clever output permutation, which hides the LCG's weaknesses. Both fit in a few lines.

Rust xorshift64 and PCG32

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The PCG32 constants follow the published reference implementation for the "pcg32" generator, with seed 42 and stream 54 as in its demo program, so you can compare the first outputs with the reference if you like. Die counts will land near 1,000 each but never exactly; that wobble is what "random" looks like. If all six counts were exactly 1,000 the generator would be too regular.

Ranges without bias, and shuffling

Turning a raw u32 into "a number from 0 to 5" with % 6 is slightly biased: 2^32 is not divisible by 6, so the first few values appear a tiny bit more often. For a game it does not matter; for statistics or fairness it does. The fix is rejection sampling: throw away values in the leftover zone at the top and draw again.

Shuffling has a similar trap. The correct algorithm is Fisher-Yates: walk from the end, swapping each element with a random earlier-or-same position. Sorting by a random key, or swapping each element with any random position, produces a non-uniform result.

Rust Unbiased range and Fisher-Yates shuffle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Because the seed is fixed, the shuffled order is the same every time you press Run. In a real application you would seed from the clock or the operating system. The rand crate does this for you, and also provides SliceRandom::shuffle and choose with the same algorithms.

Seeding from time with SystemTime::now() is acceptable for games and sampling, but it is guessable, so it is never acceptable for security. Reading /dev/urandom or using getrandom is the correct source for secrets.

Hashing: Hash, Hasher and BuildHasher

A hash function maps data of any size to a fixed-size number, called a hash. Equal inputs always give equal hashes; different inputs usually give different hashes, but collisions are unavoidable. Rust splits hashing into three traits:

  • Hash is implemented by types that can be hashed. It feeds the type's fields into a hasher. You almost always get it with #[derive(Hash)].
  • Hasher is the algorithm. It receives bytes through write and returns a u64 from finish.
  • BuildHasher creates fresh Hasher values. HashMap stores one and uses it for every key.

The standard HashMap uses RandomState, which creates DefaultHasher (currently SipHash 1-3) with random keys per map. That makes it resistant to hash flooding, where an attacker sends many keys with colliding hashes to slow your server to a crawl. The price is a bit of speed, and one important consequence: hash values and HashMap iteration order differ from run to run.

Rust DefaultHasher: equal inputs, equal hashes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

DefaultHasher::new() always uses fixed keys, so within one program version it is repeatable, but the standard library explicitly says the algorithm can change in any release. Do not store these hashes in files or databases, and do not send them over the network.

The &"rust" and String comparison works because str and String hash identically; this is a rule required for HashMap<String, V> lookups with &str to work.

Writing your own Hasher

Sometimes you want something faster than SipHash for trusted data (small integer keys in a game, say), or a hash that is stable across runs and versions (for example to route a record to a shard). Implementing Hasher takes two methods. Here is FNV-1a, a classic simple hash: start from an offset, then for each byte XOR it in and multiply by a prime.

Rust A custom FNV-1a hasher in a HashMap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Facts worth knowing:

  • FNV-1a values for "", "a" and "hello" are published test vectors, so you can check your implementation against any reference.
  • HashMap::default() is needed instead of HashMap::new(), because new exists only for the default RandomState.
  • Hash for integers writes their bytes in native endianness, and str writes the bytes plus a 0xff terminator, but a tuple of two u8 values simply writes both bytes. So the final check above is true for u8 pairs, while it would not be for Strings. Do not rely on Hash byte layouts for persistent formats; hash the bytes you define yourself.
  • Replacing the hasher removes hash-flooding protection. Only do it for keys you control. Crates such as rustc-hash (FxHash) and ahash do this carefully, and are widely used.
  • A hash is not encryption and not a password hash. For file checksums use SHA-256 from a crate such as sha2; for passwords use argon2.

Floating-point math

f64 and f32 follow the IEEE 754 standard. Most of the math functions are methods on the types (x.sqrt()), not a separate Math class. The constants live in std::f64::consts (PI, E, TAU, SQRT_2, LN_2).

Rust The f64 toolbox

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The important traps:

  • f64 is not Ord or Eq, because NaN != NaN. That is why sort() does not compile on a Vec<f64>. Use sort_by(|a, b| a.total_cmp(b)) or partial_cmp(...).unwrap() (which panics on NaN), and you cannot use floats as HashMap keys directly.
  • round() rounds halves away from zero (2.5 becomes 3, -2.5 becomes -3), unlike the "banker's rounding" some languages use. round_ties_even() exists if you need that.
  • Never compare computed floats with ==. Use a tolerance. A fixed f64::EPSILON is the right size only for values near 1.0; for big or small numbers use a relative tolerance.
  • Never use floats for money. Store cents in an integer.
  • Float-to-int as casts saturate and turn NaN into 0; 300.7_f64 as u8 is 255. See numeric conversion.

Integer math: isqrt, gcd and friends

Integer types have their own helper methods, and since Rust 1.84 isqrt computes an exact integer square root, which avoids the precision problems of going through f64. There is no built-in gcd, but Euclid's algorithm is three lines, and checked_* methods let you detect overflow instead of panicking or wrapping.

Rust isqrt, gcd, lcm and modular power

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

mod_pow uses square and multiply to compute large powers in about 64 steps for a 64-bit exponent instead of billions, and widens to u128 so the intermediate product cannot overflow. This is the core of RSA-style math and primality tests. The is_prime function tries divisors only up to the integer square root, which is why isqrt shows up here.

When to use what

You need Use
Reproducible simulation or test data A seeded PRNG you control
Games, sampling, shuffling rand crate (or a small PRNG)
Secrets, tokens, keys OS randomness via rand/getrandom, never a seeded PRNG
A HashMap key you do not control The default RandomState hasher
Fast integer keys you control FxHash-style hasher from a crate
A hash that must stay the same forever Your own explicit algorithm (FNV, or a crypto hash from a crate)
Money Integers (cents), or a decimal crate

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the standard library have no random number generator?

    Rust keeps std small. Statistical quality, speed and security trade-offs live in crates like rand and getrandom.
  2. 2. Two generators start from the same seed. What do they produce?

    A PRNG is a deterministic function of its state, so the same seed gives the same sequence. That is what makes simulations and tests reproducible.
  3. 3. Which wrapping method matches the arithmetic of an LCG on u64?

    LCGs rely on arithmetic modulo 2^64. wrapping_mul and wrapping_add do exactly that, while plain * panics on overflow in debug builds.
  4. 4. Why should you not print or store DefaultHasher values?

    The standard library reserves the right to change the hashing algorithm. HashMap itself also randomizes its keys per map. Use an explicit algorithm for stable hashes.
  5. 5. Why does vec_of_f64.sort() not compile?

    Sorting needs a total order. f64 only has PartialOrd, so use sort_by with total_cmp or partial_cmp.

Summary

  • Rust's standard library has no RNG; write a seeded PRNG (LCG, xorshift, PCG) for reproducible work and use the rand crate for the rest.
  • PRNG state updates use wrapping_* operations; take high bits from LCGs.
  • Use rejection sampling for unbiased ranges and Fisher-Yates for fair shuffles.
  • Seeded PRNGs are never suitable for secrets.
  • Hash describes what to hash, Hasher is the algorithm, BuildHasher creates hashers; HashMap defaults to randomized SipHash for flooding resistance.
  • Do not print or persist DefaultHasher values; implement an explicit hasher such as FNV-1a for stable results.
  • f64 is not Ord, == on computed floats is unreliable, and money belongs in integers.
  • Use isqrt, checked_*, rem_euclid and square-and-multiply for exact integer math.

Next: Parsing Text: Hand-Written Parsers