§4.3 — generated digits are reversed digits of k/m
ProvedCarryRNG.SWB.output_eq_reversed_digitsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-expansionrandom-number-generationsubtract-with-borrow
Let , , and . Take any Method 1 seed other than and any endpoint . There is an integer , positive exactly when is not the all-zero seed, such that the generated block , read backwards, is the opening block of the base- expansion of :
Here is the newly appended digit after steps, and is the th fractional digit. This precise finite-block form captures the paper’s tableau relation for every seed and every block length; the numerator may depend on .
Preamble
import Definitions.Def_CarryRNG_SWB_out import Definitions.Def_CarryRNG_AWC_digit import Definitions.Def_CarryRNG_SWB_modulus import Definitions.Def_CarryRNG_AWC_zeroSeed import Definitions.Def_CarryRNG_AWC_topSeed
Formal statement
namespace CarryRNG.SWB
/-- Section 4.3: every generated finite block, read backwards, starts the expansion of
a proper fraction with denominator `m = b^r - b^s + 1`. -/
theorem output_eq_reversed_digits (b : ℕ) (L : CarryRNG.AWC.Lags) (hb : 2 ≤ b)
(z : CarryRNG.AWC.State b L.r) (hz : z ≠ CarryRNG.AWC.topSeed b L.r hb) (C : ℕ) (hC : L.r + 1 ≤ C) :
∃ k : ℕ, k < modulus b L ∧ (0 < k ↔ z ≠ CarryRNG.AWC.zeroSeed b L.r hb) ∧
∀ n : ℕ, L.r + 1 ≤ n → n ≤ C →
out b L hb z n = CarryRNG.AWC.digit b (modulus b L) k (C + 1 - n) := by sorry
end CarryRNG.SWB
Source
G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), pp. 470–471, Section 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.