Draw semantics and sequential state

Terms

A cursor stores its position as (block, lane). For a block width W, the corresponding integer position is block * W + lane. Alignment may reserve unused padding words before a value. Those words still count as consumed.

bits(key, counter) addresses the raw counter directly. Public draws combine the family and block into a generator-specific counter layout.

Counter-backed state can recompute any block from its key and counter. The generator does not need mutable internal state to reach that block.

Keys, cursors, and wrappers

An AbstractImmutableRNG is an isbits key. A pure draw does not change it. Derivation and drawing use separate tagged domains. Uniforms, normals, exponentials, ranges, shuffle, and cycle use distinct family tags. This scheme separates domains and raw addresses. It does not prove mathematical independence.

RNGCursor(key) adds a global raw-word position to the stream identity. MutableRNG owns one cursor and implements Random.AbstractRNG. Both use the key directly. Derive all independent keys before sequential consumption:

children = splitrng(key, Val(4))
cursors = RNGCursor.(children)

Copying a cursor or wrapper replays the same suffix. Keep one live continuation for each logical chain unless you intend to replay it.

Global word consumption

One cursor advances across all draw families. A primitive address is (family, block, lane). Alignment consumes padding words.

cursor_position(cursor) reports the next global word position as a decimal UInt128. The terminal cursor lies after the final raw word. A positive operation past it throws StreamExhausted. An owned zero-element operation is an exact no-op, even at the terminal cursor.

Cursor nextrand* methods and owned MutableRNG methods return the same values and ending cursor. Key nextrand* methods retain a separate split-per-call continuation and produce a different stream.

Arrays and bits

Pure key arrays give each element a stable address. Owned cursor-backed Array fills reserve the full word span once. Their values match repeated scalar mutable draws in logical order. Each state model has a shape-stable law.

Logical BitArray fills consume one word per Bool, clear unused tail bits, and match repeated scalar calls. The packed alternatives ImmutableRNGs.packed_bitrand and packed_bitrand! consume one aligned UInt64 slot per 64-bit chunk. The two methods have different consumption laws. On one host, logical generation measured about 65 times slower than packed generation. Use the packed form when throughput matters.

Fixed-work integer ranges

Owned range sampling selects the raw width from the span:

• A nonempty span at most 2^32 consumes one aligned UInt64 slot and uses a 64-bit input.
• A larger 64-bit span consumes two aligned UInt64 slots and uses a 128-bit input.
• A full-width 64-bit range uses the zero span encoding, consumes two slots, and returns the high limb exactly.

For input width K, uniform integer U maps to

floor(U * span / 2^K).

The device implementation uses 32-bit limb arithmetic. It requires no device UInt128, division, retry loop, or data-dependent work.

Each output has either floor(2^K / span) or ceil(2^K / span) preimages. The maximum relative probability error is less than span / 2^K, and total variation is at most span / (4 * 2^K). Small spans have less than 2^-32 relative error. Wide 64-bit spans have less than 2^-64. At span 3 * 2^62, the 128-bit total variation is 1 / (3 * 2^65). The former one-slot law gave 1/6.

The same width rule applies to scalar draws, arrays, DiscreteUniform, shuffle, permutation, cycle, pure keys, cursors, CPU fills, and claimed device fills. Generic 128-bit ranges retain Julia's version-sensitive, variable-work Random path and have no owned accelerator claim.

Fixed work avoids data-dependent cursor consumption and device divergence from rejection sampling. Shuffle and cycle inherit the sum of their ordinal range bounds. They are not exactly uniform by contract.

Uniform, normal, and exponential grids

A Float32 uniform uses the high 24 bits on a 2^-24 grid. A Float64 uniform uses the high 53 bits on a 2^-53 grid. Both are closed at zero and open at one.

Normal draws pass an open midpoint grid to AS241. The endpoints are finite and symmetric. Exponential draws compute -log(1-u) from the owned closed-zero uniform grid. A zero input yields -0.0, so 1 / randexp(...) can be -Inf.

CPU and claimed device paths agree on raw words, transform inputs, and ending cursors. Normal and exponential values agree exactly within one backend. CPU and CUDA values may differ within the calibrated ULP bound because their transforms and contraction differ.

Distributions' owned Uniform{Float32} path uses a Float64 grid before the final conversion. Float32 rounding can return the closed upper endpoint with probability near 2^-25.

Version 0.1.0 owns pure-key randsubseq, but not cursor-backed randsubseq or any randsubseq! method. It does not own CloseOpen12. The unowned methods' primitive consumption depends on the Julia version. CloseOpen12 also uses a coarser uniform grid.

Stream compatibility

The canonical cursor record contains the generator and stream ID. All built-in IDs end in -v1. Restoration accepts a registered compatible ID and rejects an incompatible record with IncompatibleCheckpoint.

Owned fixed paths replay from a compatible canonical record. Generic Random, Distributions, Turing, and AbstractMCMC replay also depends on their exact versions and configuration. Record that wider context in a separate replay manifest.