Debian Codegraph @

reals/fast/Compress.v

raw
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.