| 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;; |