Debian Codegraph @

Formal_ineqs/informal/informal_nat.hl

raw
1 (* ========================================================================== *)
2 (* Formal verification of nonlinear inequalities in HOL Light *)
3 (* *)
4 (* Copyright (c) 2012 Alexey Solovyev *)
5 (* *)
6 (* This file is distributed under the terms of the MIT licence *)
7 (* ========================================================================== *)
8
9 (* -------------------------------------------------------------------------- *)
10 (* Informal arithmetic procedures: natural numbers *)
11 (* -------------------------------------------------------------------------- *)
12
13 (* Dependencies *)
14 needs "Formal_ineqs/misc/misc_functions.hl";;
15 needs "Formal_ineqs/misc/misc_vars.hl";;
16 needs "Formal_ineqs/arith_options.hl";;
17
18
19 (* Natural numbers *)
20
21 module type Informal_nat_sig =
22 sig
23 type nat
24 val arith_base : int
25 val mk_nat : num -> nat
26 val mk_small_nat : int -> nat
27 val dest_nat : nat -> num
28 val eq_nat : nat -> nat -> bool
29 val suc_nat : nat -> nat
30 val pre_nat : nat -> nat
31 val eq0_nat : nat -> bool
32 val gt0_nat : nat -> bool
33 val lt_nat : nat -> nat -> bool
34 val le_nat : nat -> nat -> bool
35 val add_nat : nat -> nat -> nat
36 val sub_nat : nat -> nat -> nat
37 (* If sub_and_le_nat m n = (m - n, true) if n <= m; (n - m, false) if m < n *)
38 val sub_and_le_nat : nat -> nat -> nat * bool
39 val mul_nat : nat -> nat -> nat
40 val div_nat : nat -> nat -> nat
41 val even_nat : nat -> bool
42 val odd_nat : nat -> bool
43
44 (* normalize_nat m = (n, e) s.t. m = n * base^e, e >= 0 *)
45 val normalize_nat : nat -> nat * int
46 val denormalize_nat : nat * int -> nat
47 (* hi_nat p m = (n, e) s.t. m <= n * base^e and n contains at most p "digits" *)
48 val hi_nat : int -> nat -> nat * int
49 val hi_lt_nat : int -> nat -> nat * int
50 (* lo_nat p m = (n, e) s.t. n * base^e <= m and n contains at most p "digits" *)
51 val lo_nat : int -> nat -> nat * int
52 end;;
53
54
55
56 module Informal_nat : Informal_nat_sig = struct
57
58 open Misc_functions;;
59 open Big_int;;
60
61 type nat = big_int;;
62
63 let arith_base = !Arith_options.base;;
64
65 let mk_nat n =
66 let result = big_int_of_num n in
67 if sign_big_int result < 0 then zero_big_int else result;;
68
69 let mk_small_nat n =
70 if n < 0 then zero_big_int else big_int_of_int n;;
71
72 let dest_nat = num_of_big_int;;
73
74 let eq_nat = eq_big_int;;
75
76 let suc_nat = succ_big_int;;
77
78 let pre_nat n =
79 let result = pred_big_int n in
80 if sign_big_int result < 0 then zero_big_int else result;;
81
82 let eq0_nat n = sign_big_int n = 0;;
83
84 let gt0_nat n = sign_big_int n > 0;;
85
86 let lt_nat = lt_big_int;;
87
88 let le_nat = le_big_int;;
89
90 let add_nat = add_big_int;;
91
92 let sub_nat m n =
93 let result = sub_big_int m n in
94 if sign_big_int result < 0 then zero_big_int else result;;
95
96 let sub_and_le_nat m n =
97 let result = sub_big_int m n in
98 if sign_big_int result >= 0 then (result, true) else (abs_big_int result, false);;
99
100 let mul_nat = mult_big_int;;
101
102 let div_nat = div_big_int;;
103
104 let two_big_int = big_int_of_int 2;;
105
106 let even_nat n = sign_big_int (mod_big_int n two_big_int) = 0;;
107
108 let odd_nat n = sign_big_int (mod_big_int n two_big_int) > 0;;
109
110 (*******************************)
111 (* num_exp *)
112
113 let base_nat = mk_small_nat arith_base;;
114
115 (* normalize_nat m = (n, e) s.t. m = n * base^e, e >= 0 *)
116 let normalize_nat =
117 let rec normalize n e =
118 let q, r = quomod_big_int n base_nat in
119 if sign_big_int r > 0 then
120 (n, e)
121 else
122 normalize q (succ e) in
123 fun n ->
124 if sign_big_int n = 0 then (n, 0) else normalize n 0;;
125
126
127 let denormalize_nat (n, e) =
128 mult_big_int n (power_int_positive_int arith_base e);;
129
130
131 let lo_nat pp =
132 let max = power_int_positive_int arith_base pp in
133 let rec lo m e =
134 if lt_big_int m max then
135 (m, e)
136 else
137 let q = div_big_int m base_nat in
138 lo q (succ e) in
139 fun m ->
140 if sign_big_int m = 0 then
141 (m, 0)
142 else
143 let n1, e1 = lo m 0 in
144 let n, e2 = normalize_nat n1 in
145 n, e1 + e2;;
146
147
148 let hi_nat pp =
149 if pp <= 0 then failwith "hi_nat: pp <= 0" else
150 let max = power_int_positive_int arith_base pp in
151 let rec hi m e =
152 if lt_big_int m max then
153 (m, e)
154 else
155 let q, r = quomod_big_int m base_nat in
156 if sign_big_int r = 0 then
157 hi q (succ e)
158 else
159 hi (succ_big_int q) (succ e) in
160 fun m ->
161 if sign_big_int m = 0 then
162 (m, 0)
163 else
164 let n1, e1 = hi m 0 in
165 let n, e2 = normalize_nat n1 in
166 n, e1 + e2;;
167
168
169 let hi_lt_nat pp m =
170 hi_nat pp (succ_big_int m);;
171
172
173 end;;