| 1 |
(* |
| 2 |
Copyright © 2006-2008 Russell O’Connor |
| 3 |
|
| 4 |
Permission is hereby granted, free of charge, to any person obtaining a copy of |
| 5 |
this proof and associated documentation files (the "Proof"), to deal in |
| 6 |
the Proof without restriction, including without limitation the rights to |
| 7 |
use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of |
| 8 |
the Proof, and to permit persons to whom the Proof is furnished to do so, |
| 9 |
subject to the following conditions: |
| 10 |
|
| 11 |
The above copyright notice and this permission notice shall be included in all |
| 12 |
copies or substantial portions of the Proof. |
| 13 |
|
| 14 |
THE PROOF IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| 15 |
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS |
| 16 |
FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR |
| 17 |
COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER |
| 18 |
IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
| 19 |
CONNECTION WITH THE PROOF OR THE USE OR OTHER DEALINGS IN THE PROOF. |
| 20 |
*) |
| 21 |
|
| 22 |
From Coq Require Import ZArith. |
| 23 |
Require Import CoRN.algebra.RSetoid. |
| 24 |
Require Import CoRN.metric2.Metric. |
| 25 |
Require Import CoRN.metric2.UniformContinuity. |
| 26 |
Require Import CoRN.model.totalorder.QposMinMax. |
| 27 |
Require Export CoRN.model.metric2.CRmetric. |
| 28 |
Require Import CoRN.model.metric2.Qmetric. |
| 29 |
From Coq Require Import Zdiv. |
| 30 |
|
| 31 |
Opaque CR. |
| 32 |
|
| 33 |
Local Open Scope Q_scope. |
| 34 |
Local Open Scope uc_scope. |
| 35 |
|
| 36 |
(** |
| 37 |
** Compression |
| 38 |
Compress improves the computation by reducing the size of the numerator |
| 39 |
and denominator of rational numbers. It works by increasing the |
| 40 |
requested precession, but then rounding the result to a value with a |
| 41 |
small numerator and denominator. |
| 42 |
|
| 43 |
The full euclidean algortihm would find the optimial rational approximation. |
| 44 |
But for speed we simply do division to quickly find a good rational |
| 45 |
approximation. |
| 46 |
*) |
| 47 |
Definition approximateQ (x:Q) (p:positive) := |
| 48 |
let (n,d) := x in (Z.div (n*Zpos p) (Zpos d)#p). |
| 49 |
|
| 50 |
Lemma approximateQ_correct : forall x p, |
| 51 |
ball (1#p) x (approximateQ x p). |
| 52 |
Proof. |
| 53 |
intros [n d] p. |
| 54 |
split; simpl; unfold Qle; simpl. |
| 55 |
- apply Z.le_trans with 0%Z. |
| 56 |
discriminate. |
| 57 |
apply Zmult_le_0_compat; auto with *. |
| 58 |
replace (n * Zpos p + - (n * Zpos p / Zpos d) * Zpos d)%Z |
| 59 |
with (n * Zpos p - ((n * Zpos p / Zpos d) * Zpos d))%Z by ring. |
| 60 |
apply Zle_minus_le_0. |
| 61 |
rewrite Zmult_comm. |
| 62 |
apply Z_mult_div_ge; auto with *. |
| 63 |
- rewrite Zpos_mult_morphism. |
| 64 |
apply Zmult_le_compat_r; auto with *. |
| 65 |
replace (n * Zpos p + - (n * Zpos p / Zpos d) * Zpos d)%Z |
| 66 |
with ((n*Zpos p) mod (Zpos d))%Z. |
| 67 |
destruct (Z_mod_lt (n*Zpos p) (Zpos d)); auto with *. |
| 68 |
symmetry. transitivity (n * Zpos p - (Zpos d*(n * Zpos p / Zpos d)))%Z;[ring|]. |
| 69 |
symmetry. |
| 70 |
apply -> Zeq_plus_swap. |
| 71 |
rewrite Zplus_comm. |
| 72 |
symmetry. |
| 73 |
apply Z_div_mod_eq_full. |
| 74 |
Qed. |
| 75 |
|
| 76 |
Lemma approximateQ_big : forall (z:Z) a p, ((z#1) <= a) -> (z#1) <= approximateQ a p. |
| 77 |
Proof. |
| 78 |
intros z [n d] p Ha. |
| 79 |
unfold approximateQ. |
| 80 |
unfold Qle in *. |
| 81 |
simpl in *. |
| 82 |
apply Zlt_succ_le. |
| 83 |
unfold Z.succ. |
| 84 |
apply Zmult_gt_0_lt_reg_r with (Zpos d). |
| 85 |
reflexivity. |
| 86 |
replace ((n * Zpos p / Zpos d * 1 + 1) * Zpos d)%Z |
| 87 |
with (Zpos d* (n*Zpos p/ Zpos d) + (Z.modulo (n*Zpos p) (Zpos d)) - (Z.modulo (n*Zpos p) (Zpos d)) + Zpos d)%Z |
| 88 |
by ring. |
| 89 |
rewrite <- (Z_div_mod_eq_full (n*Zpos p) (Zpos d)). |
| 90 |
apply Z.le_lt_trans with (n*1*Zpos p)%Z. |
| 91 |
replace (z*Zpos p*Zpos d)%Z with (z*Zpos d*Zpos p)%Z by ring. |
| 92 |
apply Zmult_lt_0_le_compat_r; auto with *. |
| 93 |
apply Zlt_0_minus_lt. |
| 94 |
replace (n * Zpos p - (n * Zpos p) mod (Zpos d) + Zpos d - n * 1 * Zpos p)%Z |
| 95 |
with (Zpos d - (Z.modulo (n*Zpos p) (Zpos d)))%Z by ring. |
| 96 |
rewrite <- Zlt_plus_swap. |
| 97 |
ring_simplify. |
| 98 |
assert (X:(Zpos d >0)%Z) by auto with *. |
| 99 |
destruct (Z_mod_lt (n*Zpos p) _ X). |
| 100 |
assumption. |
| 101 |
Qed. |
| 102 |
|
| 103 |
(** Compress doubles the requried precision and uses the extra leway to |
| 104 |
round the rational number. *) |
| 105 |
Definition compress_raw (x:CR) (e:QposInf) : Q := |
| 106 |
match e with |
| 107 |
| QposInfinity => approximate x e |
| 108 |
| Qpos2QposInf e => |
| 109 |
let (n,d) := proj1_sig e in |
| 110 |
match (Z.succ (Z.div (2*Zpos d) n)) with |
| 111 |
Zpos p => approximateQ (approximate x (Qpos2QposInf (exist (Qlt 0) (1#p) eq_refl))) p |
| 112 |
|_ => approximate x e |
| 113 |
end |
| 114 |
end. |
| 115 |
|
| 116 |
Lemma compress_raw_prop : forall x (e:Qpos), |
| 117 |
ball (proj1_sig e) x (Cunit (compress_raw x e)). |
| 118 |
Proof. |
| 119 |
intros x. intros [[n d] dpos]. |
| 120 |
destruct n as [|n|n]. inversion dpos. 2: inversion dpos. |
| 121 |
simpl. |
| 122 |
assert (0 < Z.succ (Zpos (d~0)%positive / Zpos n))%Z as zpos. |
| 123 |
{ unfold Z.succ. |
| 124 |
apply (Z.lt_le_trans _ (0+1)). reflexivity. |
| 125 |
apply Z.add_le_mono_r. apply Z_div_pos. |
| 126 |
reflexivity. discriminate. } |
| 127 |
destruct (Z.succ (Zpos (xO d) / Zpos n)) eqn:Hp. |
| 128 |
- exfalso. discriminate. |
| 129 |
- apply ball_weak_le with (2#p). |
| 130 |
unfold Qle. |
| 131 |
simpl. |
| 132 |
rewrite Zpos_mult_morphism. |
| 133 |
rewrite <- Hp. |
| 134 |
unfold Z.succ. |
| 135 |
rewrite Zmult_plus_distr_r. |
| 136 |
apply Zle_0_minus_le. |
| 137 |
replace (Zpos n * (Zpos (d~0)%positive / Zpos n) + Zpos n * 1 - Zpos (d~0)%positive)%Z |
| 138 |
with (Zpos n - (Zpos (xO d) - Zpos n * (Zpos (xO d) / Zpos n)))%Z by ring. |
| 139 |
apply Zle_minus_le_0. |
| 140 |
replace (Zpos (d~0)%positive - Zpos n * (Zpos (d~0)%positive / Zpos n))%Z |
| 141 |
with (Zpos (xO d) mod (Zpos n))%Z. |
| 142 |
destruct (Z_mod_lt (Zpos (xO d)) (Zpos n)); auto with *. |
| 143 |
symmetry. transitivity (Zpos (xO d) - (Zpos n*(Zpos (xO d) / Zpos n)))%Z;[ring|]. |
| 144 |
symmetry; apply -> Zeq_plus_swap. |
| 145 |
rewrite Zplus_comm. |
| 146 |
symmetry. |
| 147 |
apply Z_div_mod_eq_full. |
| 148 |
assert (QposEq (2#p) ((1#p)+(1#p))). |
| 149 |
{ unfold QposEq. simpl. |
| 150 |
repeat rewrite -> Qmake_Qdiv. |
| 151 |
unfold Qdiv. |
| 152 |
ring. } |
| 153 |
apply (ball_wd _ H _ _ (reflexivity _) _ _ (reflexivity _)). clear H. |
| 154 |
eapply ball_triangle with (Cunit (approximate x (Qpos2QposInf (1#p)))). |
| 155 |
apply ball_approx_r. |
| 156 |
Transparent CR. |
| 157 |
change (ball (m:=Complete Q_as_MetricSpace) |
| 158 |
(1 # p) (Cunit (approximate x (Qpos2QposInf (1 # p)))) |
| 159 |
(Cunit (approximateQ (approximate x (Qpos2QposInf (1 # p))) p))). |
| 160 |
rewrite -> ball_Cunit. |
| 161 |
apply approximateQ_correct. |
| 162 |
- exfalso. discriminate. |
| 163 |
Qed. |
| 164 |
|
| 165 |
Lemma compress_raw_prf : forall x, |
| 166 |
is_RegularFunction (@ball Q_as_MetricSpace) (compress_raw x). |
| 167 |
Proof. |
| 168 |
intros x e1 e2. |
| 169 |
rewrite <- ball_Cunit. |
| 170 |
eapply ball_triangle;[|apply compress_raw_prop]. |
| 171 |
apply ball_sym. |
| 172 |
apply compress_raw_prop. |
| 173 |
Qed. |
| 174 |
|
| 175 |
Definition compress_fun (x:CR) : CR := |
| 176 |
Build_RegularFunction (compress_raw_prf x). |
| 177 |
|
| 178 |
(** Compress is equivalent to the identity function. *) |
| 179 |
Lemma compress_fun_correct : forall x, (compress_fun x==x)%CR. |
| 180 |
Proof. |
| 181 |
intros x. |
| 182 |
apply regFunEq_equiv, regFunEq_e. |
| 183 |
intros e. |
| 184 |
unfold compress_fun. |
| 185 |
unfold approximate at 1. |
| 186 |
rewrite <- ball_Cunit. |
| 187 |
eapply ball_triangle;[|apply ball_approx_r]. |
| 188 |
apply ball_sym. |
| 189 |
apply compress_raw_prop. |
| 190 |
Qed. |
| 191 |
|
| 192 |
Lemma compress_uc : is_UniformlyContinuousFunction compress_fun Qpos2QposInf. |
| 193 |
Proof. |
| 194 |
intros e x y H. |
| 195 |
do 2 rewrite -> compress_fun_correct. |
| 196 |
assumption. |
| 197 |
Qed. |
| 198 |
|
| 199 |
Definition compress : CR --> CR := |
| 200 |
Build_UniformlyContinuousFunction compress_uc. |
| 201 |
|
| 202 |
Lemma compress_correct : forall x, (compress x==x)%CR. |
| 203 |
Proof. |
| 204 |
intros x. |
| 205 |
apply compress_fun_correct. |
| 206 |
Qed. |