LAWS_mul.bend

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

1# bend-osdev-word64's laws of multiplication, for every input: the high
2# half of a 32-bit product (W64.mulhi), and W64.mul as the low 64 bits of the
3# product of the values. Proved in PROOF_mul.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# Multiplication. W64.mulhi(a, b) is the high 32 bits of the product of two
9# 32-bit words: with the low 32 bits (U32.mul), the whole product. W64.mul
10# is the product modulo 2^64: its value is the low 64 bits of the product of
11# the values (U32Nat.low, from bend-osdev-u32), what wraps is 2^64 times the
12# rest, and with the product no more than a word's value nothing wraps.
13law mulhi_value:
14  for +a: U32
15  for +b: U32
16  {Nat.add(U32.to_nat(U32.mul(a, b)), U.U32Nat.dbl(32n, U32.to_nat(W.W64.mulhi(a, b)))) == Nat.mul(U32.to_nat(a), U32.to_nat(b)) : Nat}
17
18law mul_wrap:
19  for +a: W.W64
20  for +b: W.W64
21  {Nat.add(W.W64.to_nat(W.W64.mul(a, b)), U.U32Nat.dbl(64n, U.U32Nat.high(64n, Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b))))) == Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)) : Nat}
22
23law mul_low:
24  for +a: W.W64
25  for +b: W.W64
26  {W.W64.to_nat(W.W64.mul(a, b)) == U.U32Nat.low(64n, Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b))) : Nat}
27
28law mul_value:
29  for +a: W.W64
30  for +b: W.W64
31  for +c: W.W64
32  for h: {Nat.is_le(Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)), W.W64.to_nat(c)) == True{} : Bool}
33  {W.W64.to_nat(W.W64.mul(a, b)) == Nat.mul(W.W64.to_nat(a), W.W64.to_nat(b)) : Nat}