LAWS_div.bend

bend-osdev-word64@0.1.1.0 · 29 lines · 4 definitions

1# bend-osdev-word64's laws of division, for every input: W64.div and
2# W64.mod are the Nat quotient and remainder, and division by 0 gives 0 and
3# the dividend. Proved in PROOF_div.bend.
4import Base
5import bend-osdev-u32@0.1.0.0/u32.bend as U
6import bend-osdev-word64@0.1.1.0/word64.bend as W
7
8# Division (shift and subtract, 64 steps): for b not 0, the quotient and the
9# remainder are the Nat ones, a = q b + r with r < b; by 0, the quotient is 0
10# and the remainder a.
11law divmod_value:
12  for +a: W.W64
13  for +b: W.W64
14  for h: {W.W64.is_zero(b) == False{} : Bool}
15  {Nat.add(Nat.mul(W.W64.to_nat(W.W64.div(a, b)), W.W64.to_nat(b)), W.W64.to_nat(W.W64.mod(a, b))) == W.W64.to_nat(a) : Nat}
16
17law mod_lt:
18  for +a: W.W64
19  for +b: W.W64
20  for h: {W.W64.is_zero(b) == False{} : Bool}
21  {Nat.is_lt(W.W64.to_nat(W.W64.mod(a, b)), W.W64.to_nat(b)) == True{} : Bool}
22
23law div_zero:
24  for +a: W.W64
25  {W.W64.div(a, W.W64.zero()) == W.W64.zero() : W.W64}
26
27law mod_zero:
28  for +a: W.W64
29  {W.W64.mod(a, W.W64.zero()) == a : W.W64}