What one Philox round actually does

A conventional generator holds internal state ss and computes (si+1,xi)=f(si)(s_{i+1}, x_i) = f(s_i). Getting the nnth output means applying ff nn times, and the state you would have to checkpoint is whatever ff happens to keep in memory. For std::mt19937 that is 624 words plus an index, in an order the C++ standard never pinned down.

Philox replaces the recurrence with a keyed bijection over a counter:

xn=b(c0+n,k)x_n = b(\mathbf{c}_0 + n, \mathbf{k})

Constant-time seek, independent substreams per worker, a checkpoint that survives a change of machine: every claim in the paper falls out of that one line, because there is no accumulated state left to disagree about. That leaves one thing to look at. bb itself.

One round of the Philox4x32-10 bijectionFour 32-bit counter words. Two are multiplied by fixed constants into 64-bit products, each split into a high and a low half. The high halves are XORed with an unmultiplied word and a key word. The four results are written back in shuffled order, and the key is bumped by odd constants.c₀c₁c₂c₃k₀k₁counterkey× M₀h₀l₀× M₁h₁l₁0xD2511F530xCD9E8D57⊕⊕c₀′c₁′c₂′c₃′h₁ ⊕ c₁ ⊕ k₀l₁h₀ ⊕ c₃ ⊕ k₁l₀k₀ += W₀k₁ += W₁W₀ 0x9E3779B9W₁ 0xBB67AE85
State.

Ten of those rounds is Philox4x32-10.

The wide multiply is the whole cost. Each round does two 32×32→6432 \times 32 \rightarrow 64 multiplications and needs both halves of each product. Scalar code gets that for free, because the hardware produces a 64-bit result whether you asked for one or not. SIMD code does not: the vector instruction sets hand you the low halves or the high halves, never both, so a round costs two instructions where the scalar version costs one. That asymmetry is why naive vectorization disappoints, and working around it is most of what the library does.

Nothing here depends on order. Round rr reads the output of round r−1r-1 and a key derived from the seed, and nothing else. Ask for the block at counter 101210^{12} and it costs what the block at counter 00 costs: you add 101210^{12} to a 128-bit integer and run the ten rounds. That is why discard is O(1)\mathcal{O}(1). It is also why two threads on disjoint counter ranges never have to talk to each other.