~/bend-docscommunity

proofs/math/random/wrappers.bend checks

raw source on the hub · import bend-collections-laws-math@1.0.0.0/proofs/math/random/wrappers.bend as Wrappers

26 imports
import Base
import ../../../spec/lib/common.bend as C
import ../../../spec/math/w64.bend as SW
import ../../../spec/math/random/source.bend as SRC
import ../../../spec/math/random.bend as SRM
import ../../../src/math/u64.bend as W
import ../../../src/math/w64.bend as X
import ../../../src/math/random/rand.bend as R
import ../../lib/nat.bend as N
import ../../lib/logic.bend as L
import ../../lib/u32.bend as U
import ../../lib/lemmas/spec/numeric.bend as S
import ../typed/width.bend as WW
import ../typed/u32laws.bend as LW
import ../typed/w64add.bend as WA
import ../typed/f64bits.bend as FB
import ../typed/w64clz.bend as WC
import ../typed/w64sh.bend as SH
import ../typed/w64div.bend as W64D
import ../u64/u64div.bend as PD
import ../typed/w64mul.bend as W64M
import ../../lib/word.bend as WD
import ../../lib/arith.bend as LA
import ../natural/arith.bend as AR
import ./bounded.bend as MR
import ./lemire.bend as LE

Definitions

def v source · line 33 · raw

@+x:U32 -> Nat

def val source · line 36 · raw

@+l:U32 -> @+h:U32 -> Nat

def u32_p source · line 41 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> {U32.to_nat(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(U32, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.top32(S, p))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.high(32n, 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random/source.fst64(S, p))) : Nat}

def low63_v source · line 53 · raw

@+l:U32 -> @+h:U32 -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64{l, U32.and(h, 2147483647)}) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(63n, val(l, h)) : Nat}

def i64_p source · line 64 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.low63(S, p))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(63n, 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random/source.fst64(S, p))) : Nat}

def half_bv source · line 76 · raw

@+b:Bool -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.half(0xf86f5f1d9a594d5a5cff999100e01d03/proofs/lib/lemmas/spec/numeric.bit_value(b)) == 0n : Nat}

def shr_half source · line 84 · raw

@+x:U32 -> {v(U32.shr(x)) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.half(v(x)) : Nat}

x >> 1 is half of x

def i32_p source · line 93 · raw

@-S:Data -> @p:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> {U32.to_nat(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(U32, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.top31(S, p))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.high(33n, 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random/source.fst64(S, p))) : Nat}

def lo_le source · line 110 · raw

@-S:Data -> @r:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> {Nat.is_le(U32.to_nat(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(U32, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.lo32(S, r))), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S, r))) == True{} : Bool}

def nz_word source · line 117 · raw

@+n:U32 -> @+hn:{U32.is_zero(n) == False{} : Bool} -> {0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.is_zero(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64{n, 0}) == False{} : Bool}

def vv source · line 131 · raw

@+x:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> Nat

def s32 source · line 134 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+x:Nat -> {Nat.mul(Nat.mul(x, 65536n), 65536n) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(32n, x) : Nat}

def n48v source · line 140 · raw

@+one:Nat -> @+h1:{one == 1n : Nat} -> @+a:0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64 -> {0xf86f5f1d9a594d5a5cff999100e01d03/src/math/w64.n48(a) == vv(a) : Nat}

def fits0 source · line 146 · raw

@+a:Nat -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(a, 0n) == True{} : Bool}

def fits_shift source · line 151 · raw

@+a:Nat -> @+k:Nat -> @+x:Nat -> @+h:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(k, x) == True{} : Bool} -> {0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(Nat.add(a, k), 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.shift(a, x)) == True{} : Bool}

x < 2^k gives x 2^a < 2^(a + k)

def sh8 source · line 154 · raw

@k:Nat -> Nat

def div256 source · line 161 · raw

@+n:Nat -> {Nat.div(n, 256n) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.high(8n, n) : Nat}

def mod256 source · line 164 · raw

@+n:Nat -> {Nat.mod(n, 256n) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(8n, n) : Nat}

def byte_v source · line 174 · raw

@+n:Nat -> {v(U32.from_nat(Nat.mod(n, 256n))) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(8n, n) : Nat}

def wgo source · line 179 · raw

@+k:Nat -> @+n:Nat -> @+hk:{Nat.is_le(sh8(k), 32n) == True{} : Bool} -> {v(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.w_go(k, n)) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.low(sh8(k), n) : Nat}

the words of w_go are the low 8k bits, for 8k <= 32

def skip_v source · line 207 · raw

@+k:Nat -> @+n:Nat -> {0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.skip(k, n) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.high(sh8(k), n) : Nat}

skip(k, n) = n div 2^(8k)

def nat64_v source · line 219 · raw

@+n:Nat -> @+hn:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(64n, n) == True{} : Bool} -> {vv(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.nat64(n)) == n : Nat}

THEOREM: nat64(n) denotes n, for n < 2^64

def n48_p source · line 231 · raw

@-S:Data -> @r:Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S) -> {0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(Nat, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.to_nat(S, r)) == 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/w64.value(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S, r)) : Nat}

def plus_fst source · line 251 · raw

@-S:Data -> @+lo:Nat -> @r:Pair(Nat, S) -> {0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(Nat, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.plus(S, lo, r)) == Nat.add(lo, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(Nat, S, r)) : Nat}

def lt_pos source · line 256 · raw

@+a:Nat -> @+b:Nat -> @+h:{Nat.is_lt(a, b) == True{} : Bool} -> {Nat.is_lt(0n, Nat.sub(b, a)) == True{} : Bool}

Templates

template uint32_value source · line 48 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.Uint32.value(S, next, s)

template int64_value source · line 71 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.Int64.value(S, next, s)

template int32_value source · line 105 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.Int32.value(S, next, s)

template uint32n_lt source · line 121 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> @+n:U32 -> @+hn:{U32.is_zero(n) == False{} : Bool} -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.Uint32n.lt(S, next, s, n, hn)

template intn_pos source · line 236 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> @+n:Nat -> @+hn:{Nat.is_lt(0n, n) == True{} : Bool} -> @+hw:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(64n, n) == True{} : Bool} -> {Nat.is_lt(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.fst(Nat, S, 0xf86f5f1d9a594d5a5cff999100e01d03/src/math/random/rand.intn_z(S, next, s, n, False{})), n) == True{} : Bool}

template intn_lt source · line 245 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> @+n:Nat -> @+hn:{Nat.is_lt(0n, n) == True{} : Bool} -> @+hw:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(64n, n) == True{} : Bool} -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.Intn.lt(S, next, s, n, hn, hw)

template int_range_bounds source · line 265 · raw

@-S:Data -> @-next:(@_:S -> Pair(0xf86f5f1d9a594d5a5cff999100e01d03/src/math/u64.U64, S)) -> @+s:S -> @+lo:Nat -> @+hi:Nat -> @+h:{Nat.is_lt(lo, hi) == True{} : Bool} -> @+hw:{0xf86f5f1d9a594d5a5cff999100e01d03/spec/lib/common.fits(64n, Nat.sub(hi, lo)) == True{} : Bool} -> 0xf86f5f1d9a594d5a5cff999100e01d03/spec/math/random.IntRange.bounds(S, next, s, lo, hi, h, hw)