source: Deliverables/D4.1/Matita/Arithmetic.ma @ 274

Last change on this file since 274 was 274, checked in by mulligan, 9 years ago

First attempt at sub8_with_c complete.

File size: 5.3 KB
Line 
1include "Universes.ma".
2include "Plogic/equality.ma".
3include "Connectives.ma".
4include "Nat.ma".
5include "Exponential.ma".
6include "Bool.ma".
7include "BitVector.ma".
8include "List.ma".
9
10ndefinition one ≝ S Z.
11ndefinition two ≝ (S(S(Z))).
12ndefinition three ≝ two + one.
13ndefinition four ≝ two + two.
14ndefinition five ≝ three + two.
15ndefinition six ≝ three + three.
16ndefinition seven ≝ three + four.
17ndefinition eight ≝ four + four.
18ndefinition nine ≝ five + four.
19ndefinition ten ≝ five + five.
20ndefinition eleven ≝ six + five.
21ndefinition twelve ≝ six + six.
22ndefinition thirteen ≝ seven + six.
23ndefinition fourteen ≝ seven + seven.
24ndefinition fifteen ≝ eight + seven.
25ndefinition sixteen ≝ eight + eight.
26ndefinition seventeen ≝ nine + eight.
27ndefinition eighteen ≝ nine + nine.
28ndefinition nineteen ≝ ten + nine.
29ndefinition one_hundred_and_twenty_eight ≝ sixteen * eight.
30ndefinition two_hundred_and_fifty_six ≝
31  one_hundred_and_twenty_eight + one_hundred_and_twenty_eight.                                         
32   
33ndefinition nat_of_bool ≝
34  λb: Bool.
35    match b with
36      [ false ⇒ Z
37      | true ⇒ S Z
38      ].
39   
40ndefinition add_n_with_carry:
41      ∀n: Nat. ∀b, c: BitVector n. ∀carry: Bool. Cartesian (BitVector n) (List Bool) ≝
42  λn: Nat.
43  λb: BitVector n.
44  λc: BitVector n.
45  λcarry: Bool.
46    let b_as_nat ≝ nat_of_bitvector n b in
47    let c_as_nat ≝ nat_of_bitvector n c in
48    let carry_as_nat ≝ nat_of_bool carry in
49    let result_old ≝ b_as_nat + c_as_nat + carry_as_nat in
50    let ac_flag ≝ ((modulus b_as_nat ((S (S Z)) * n)) +
51                  (modulus c_as_nat ((S (S Z)) * n)) +
52                  c_as_nat) ≥ ((S (S Z)) * n) in
53    let bit_xxx ≝ (((modulus b_as_nat ((S (S Z))^(n - (S Z)))) +
54                  (modulus c_as_nat ((S (S Z))^(n - (S Z)))) +
55                  c_as_nat) ≥ ((S (S Z))^(n - (S Z)))) in
56    let result ≝ modulus result_old ((S (S Z))^n) in
57    let cy_flag ≝ (result_old ≥ ((S (S Z))^n)) in
58    let ov_flag ≝ exclusive_disjunction cy_flag bit_xxx in
59      ? (mk_Cartesian (BitVector n) ? (? (bitvector_of_nat n result))
60                          (cy_flag :: ac_flag :: ov_flag :: Empty Bool)).
61    #H; nassumption;
62nqed.
63
64naxiom less_than_or_equal_b: Nat → Nat → Bool.
65naxiom ior: Bool → Bool → Bool.
66naxiom neg: Bool → Bool.
67naxiom con: Bool → Bool → Bool.
68naxiom eq: Nat → Nat → Bool.
69
70ndefinition sub_8_with_carry: ∀b,c: BitVector eight. ∀carry: Bool. Cartesian (BitVector eight) (List Bool) ≝
71  λb: BitVector eight.
72  λc: BitVector eight.
73  λcarry: Bool.
74    let b_as_nat ≝ nat_of_bitvector eight b in
75    let c_as_nat ≝ nat_of_bitvector eight c in
76    let carry_as_nat ≝ nat_of_bool carry in
77    let temporary ≝ minus (modulus b_as_nat sixteen) (modulus c_as_nat sixteen) in
78    let ac_flag ≝ ior
79                    (neg (con (less_than_or_equal_b (modulus b_as_nat sixteen) (modulus c_as_nat sixteen)) (less_than_or_equal_b temporary carry_as_nat)))
80                    (con (con (eq b_as_nat Z) (eq c_as_nat Z)) (eq carry_as_nat Z)) in
81    let bit_six ≝ ior
82                    (neg (con (less_than_or_equal_b (modulus b_as_nat one_hundred_and_twenty_eight) (modulus c_as_nat one_hundred_and_twenty_eight)) (less_than_or_equal_b temporary carry_as_nat)))
83                    (con (con (eq b_as_nat Z) (eq c_as_nat Z)) (eq carry_as_nat Z)) in
84    let old_result_1 ≝ b_as_nat - c_as_nat in
85    let old_result_2 ≝ old_result_1 - carry_as_nat in
86    let ov_flag ≝ exclusive_disjunction carry bit_six in
87      match less_than_or_equal_b b_as_nat c_as_nat with
88        [ true ⇒
89          match less_than_or_equal_b old_result_1 carry_as_nat with
90            [ true ⇒
91              let cy_flag ≝ false in
92                mk_Cartesian … (bitvector_of_nat eight old_result_2) (cy_flag :: ac_flag :: ov_flag :: (Empty Bool))
93            | false ⇒
94              let cy_flag ≝ true in
95              let new_result ≝ b_as_nat + two_hundred_and_fifty_six - c_as_nat - carry_as_nat in
96                mk_Cartesian … (bitvector_of_nat eight new_result) (cy_flag :: ac_flag :: ov_flag :: (Empty Bool))
97            ]
98        | false ⇒
99            let cy_flag ≝ true in
100            let new_result ≝ b_as_nat + two_hundred_and_fifty_six - c_as_nat - carry_as_nat in
101              mk_Cartesian … (bitvector_of_nat eight new_result) (cy_flag :: ac_flag :: ov_flag :: (Empty Bool))
102        ].
103   
104ndefinition add_8_with_carry ≝ add_n_with_carry eight.
105ndefinition add_16_with_carry ≝ add_n_with_carry sixteen.
106
107ndefinition increment ≝
108  λn: Nat.
109  λb: BitVector n.
110    let b_as_nat ≝ (nat_of_bitvector n b) + (S Z) in
111    let overflow ≝ b_as_nat ≥ (S (S Z))^n in
112      match overflow with
113        [ false ⇒ bitvector_of_nat n b_as_nat
114        | true ⇒ zero n
115        ].
116       
117ndefinition decrement ≝
118  λn: Nat.
119  λb: BitVector n.
120    let b_as_nat ≝ nat_of_bitvector n b in
121      match b_as_nat with
122        [ Z ⇒ max n
123        | S o ⇒ bitvector_of_nat n o
124        ].
125       
126alias symbol "greater_than_or_equal" (instance 1) = "Nat greater than or equal prop".
127
128ndefinition bitvector_of_bool:
129      ∀n: Nat. ∀b: Bool. BitVector n ≝
130  λn: Nat.
131  λb: Bool.
132    ? (pad (n - (S Z)) (S Z) (Cons Bool ? b (Empty Bool))).
133  nrewrite > (plus_minus_inverse_right n ?);
134  #H;
135  nassumption;
136nqed.
Note: See TracBrowser for help on using the repository browser.