Debian Codegraph @

reals/fast/CRcos.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 Require Import CoRN.algebra.RSetoid.
23 Require Import CoRN.metric2.Metric.
24 Require Import CoRN.metric2.UniformContinuity.
25 Require Export CoRN.reals.fast.CRArith.
26 Require Import CoRN.reals.fast.CRsin.
27 Require Import CoRN.reals.fast.CRpi.
28 Require Import CoRN.reals.fast.CRIR.
29 Require Import CoRN.reals.fast.Compress.
30 From Coq Require Import Qpower.
31 Require Import CoRN.model.ordfields.Qordfield.
32 From Coq Require Import Qround.
33 Require Import CoRN.transc.Pi.
34 Require Import CoRN.reals.fast.ModulusDerivative.
35 Require Import CoRN.reals.fast.ContinuousCorrect.
36 Require Import CoRN.model.metric2.Qmetric.
37 Require Import CoRN.transc.SinCos.
38 Require Import CoRN.tactics.CornTac.
39 Require Import MathClasses.interfaces.abstract_algebra.
40
41 (* Backwards compatibility for Hint Rewrite locality attributes *)
42 Set Warnings "-unsupported-attributes".
43
44 Opaque inj_Q CR Qmin Qmax.
45
46 Local Open Scope Q_scope.
47 Local Open Scope uc_scope.
48
49 (**
50 ** Cosine
51 Cosine is defined in terms of Sine. [cos x = 1 - 2*(sin(x/2))^2].
52 But cosine is still first defined on the rational numbers, and lifted
53 to the real numbers. *)
54
55 Section Cos_Poly.
56
57 Definition cos_poly_fun (x:Q) :Q := 1 - (2#1) * x * x.
58
59 Global Instance: Proper ((=) ==> (=)) cos_poly_fun.
60 Proof. unfold cos_poly_fun. solve_proper. Qed.
61
62 Lemma cos_poly_fun_correct : forall (q:Q),
63 inj_Q IR (cos_poly_fun q)[=][1][-]Two[*](inj_Q IR q[^]2).
64 Proof.
65 intros q.
66 unfold cos_poly_fun.
67 stepr (inj_Q IR ([1][-]Two*q^2)).
68 apply inj_Q_wd.
69 unfold cg_minus; simpl; ring.
70 stepr (inj_Q IR ([1])[-]inj_Q IR (Two[*]q ^ 2))%Q.
71 apply inj_Q_minus.
72 apply cg_minus_wd.
73 rstepr (nring 1:IR).
74 apply (inj_Q_nring IR 1).
75 stepr (inj_Q IR Two[*]inj_Q IR (q^2)).
76 apply inj_Q_mult.
77 apply mult_wd.
78 apply (inj_Q_nring IR 2).
79 apply (inj_Q_power IR q 2).
80 Qed.
81
82 Definition cos_poly_modulus (e:Qpos) := Qpos2QposInf ((1#4)*e).
83
84 Lemma DoneMinusX2 : Derivative (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q)))
85 (inj_Q_less _ (-1) 1 eq_refl)
86 ([-C-]([1]:IR){-}(Two:IR){**}FId{^}2)
87 ([-C-]([0]:IR){-}(Two:IR){**}((nring 2){**}([-C-][1]{*}FId{^}1))).
88 Proof.
89 apply Derivative_minus.
90 apply Derivative_const.
91 apply Derivative_scal.
92 apply Derivative_nth.
93 apply Derivative_id.
94 Qed.
95
96 Lemma cos_poly_prf
97 : @is_UniformlyContinuousFunction
98 Q_as_MetricSpace Q_as_MetricSpace
99 (fun x => cos_poly_fun (QboundAbs (1#1) x)) cos_poly_modulus.
100 Proof.
101 apply (fun a => is_UniformlyContinuousD_Q
102 (Some (-(1))%Q)
103 (Some (1:Q)) eq_refl _ _ DoneMinusX2 cos_poly_fun a (4#1)).
104 simpl; intros q _ _.
105 apply cos_poly_fun_correct.
106 simpl; intros x' _ [Hx0 Hx1].
107 set (x:=(inj_Q IR x')) in *.
108 stepr (Four:IR); [| now (apply eq_symmetric; apply (inj_Q_nring IR 4))].
109 stepl (ABSIR ([--](Four[*]x))); [| now (apply AbsIR_wd; rational)].
110 stepl (ABSIR (Four[*]x)); [| now apply AbsIR_inv].
111 rstepr (Four[*][1]:IR).
112 apply AbsSmall_imp_AbsIR.
113 apply mult_resp_AbsSmall.
114 apply nring_nonneg.
115 split.
116 stepl ([--](pring IR 1)[/][0][+][1][//]den_is_nonzero IR (-1#1)).
117 assumption.
118 unfold pring; simpl; rational.
119 stepr (pring IR 1[/][0][+][1][//]den_is_nonzero IR 1).
120 assumption.
121 unfold pring; simpl; rational.
122 Qed.
123
124 Definition cos_poly_uc : Q_as_MetricSpace --> Q_as_MetricSpace :=
125 Build_UniformlyContinuousFunction cos_poly_prf.
126
127 Definition cos_poly : CR --> CR := Cmap QPrelengthSpace cos_poly_uc.
128
129 Lemma cos_poly_correct : forall x, AbsSmall (inj_Q IR (1)) x -> (IRasCR ([1][-]Two[*]x[^]2)==cos_poly (IRasCR x))%CR.
130 Proof.
131 intros x Hx.
132 assert (Y:Continuous (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))) ([-C-]([1]:IR){-}(Two:IR){**}FId{^}2)).
133 eapply Derivative_imp_Continuous.
134 apply DoneMinusX2.
135 apply: (ContinuousCorrect
136 (I:=(clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))))
137 (inj_Q_less _ (-1) 1 eq_refl) Y);
138 [|repeat constructor|].
139 intros q Hq Hq0.
140 transitivity (IRasCR (inj_Q IR (cos_poly_fun q)));[|apply IRasCR_wd; apply cos_poly_fun_correct].
141 simpl.
142 change (' q)%CR with (Cunit_fun Q_as_MetricSpace q).
143 rewrite -> Cmap_fun_correct.
144 rewrite -> MonadLaw3.
145 rewrite -> IR_inj_Q_as_CR.
146 rewrite -> CReq_Qeq.
147 simpl.
148 unfold cos_poly_fun.
149 setoid_replace (Qmax (- (1)) (Qmin (1 # 1) q)) with q.
150 reflexivity.
151 setoid_replace (Qmin (1 # 1) q) with q.
152 rewrite <- Qle_max_r.
153 apply leEq_inj_Q with IR.
154 destruct Hq0; assumption.
155 rewrite <- Qle_min_r.
156 apply leEq_inj_Q with IR.
157 destruct Hq0; assumption.
158 destruct Hx; split;[stepl [--](inj_Q IR (1:Q)); [| now apply eq_symmetric; apply inj_Q_inv]|];assumption.
159 Qed.
160
161 Lemma Cos_double_angle : forall x, (Cos(Two[*]x)[=][1][-]Two[*]Sin x[^]2).
162 Proof.
163 intros x.
164 csetoid_replace (Two[*]x) (x[+]x);[|rational].
165 csetoid_rewrite (Cos_plus x x).
166 set (sx:=Sin x).
167 set (cx:=Cos x).
168 rstepl ((cx[^]2)[-](sx[^]2)).
169 unfold cg_minus.
170 csetoid_replace (cx[^]2) ([1][-]sx[^]2).
171 rational.
172 apply cg_inv_unique_2.
173 rstepl ((cx[^]2[+]sx[^]2)[-][1]).
174 apply x_minus_x.
175 apply FFT.
176 Qed.
177
178 End Cos_Poly.
179
180 Definition rational_cos (x:Q) := cos_poly (rational_sin (x/2)).
181
182 Lemma rational_cos_correct_aux a :
183 (cos_poly (IRasCR (Sin (inj_Q IR (a / 2)))) == IRasCR (Cos (inj_Q IR a)))%CR.
184 Proof.
185 rewrite <- cos_poly_correct.
186 apply IRasCR_wd.
187 csetoid_rewrite_rev (Cos_double_angle (inj_Q IR (a/2))).
188 apply Cos_wd.
189 csetoid_replace (Two:IR) (inj_Q IR (2:Q));[|apply eq_symmetric; apply (inj_Q_nring IR 2)].
190 stepl (inj_Q IR (2*(a/2))); [| now apply inj_Q_mult].
191 apply inj_Q_wd.
192 simpl; field; discriminate.
193 apply AbsIR_imp_AbsSmall.
194 stepr (nring 1:IR); [| now (apply eq_symmetric; apply (inj_Q_nring IR 1))].
195 rstepr ([1]:IR).
196 apply AbsIR_Sin_leEq_One.
197 Qed.
198
199 (** Cosine is correct. *)
200 Lemma rational_cos_correct : forall (a:Q),
201 (rational_cos a == IRasCR (Cos (inj_Q IR a)))%CR.
202 Proof.
203 intros a.
204 unfold rational_cos.
205 rewrite -> rational_sin_correct.
206 apply rational_cos_correct_aux.
207 Qed.
208
209 Lemma rational_cos_sin a :
210 cos_poly (rational_sin (a / 2)) = rational_cos a.
211 Proof.
212 rewrite rational_sin_correct, rational_cos_correct.
213 now apply rational_cos_correct_aux.
214 Qed.
215
216 Definition cos_uc_prf : @is_UniformlyContinuousFunction
217 Q_as_MetricSpace CR rational_cos Qpos2QposInf.
218 Proof.
219 apply (is_UniformlyContinuousFunction_wd) with (fun x => rational_cos x) (Qscale_modulus (1#1)).
220 reflexivity.
221 intros x.
222 simpl.
223 autorewrite with QposElim.
224 change (/1) with 1.
225 replace RHS with (proj1_sig x) by simpl; ring.
226 apply Qle_refl.
227 apply (is_UniformlyContinuousD None None I _ _ (Derivative_Cos I) rational_cos).
228 intros q [] _.
229 apply rational_cos_correct.
230 intros x [] _.
231 stepr ([1]:IR).
232 change (AbsIR ([--](Sin x))[<=][1]).
233 stepl (AbsIR (Sin x)); [| now apply AbsIR_inv].
234 apply AbsIR_Sin_leEq_One.
235 rstepl (nring 1:IR).
236 apply eq_symmetric.
237 apply (inj_Q_nring IR 1).
238 Qed.
239
240 Definition cos_uc : Q_as_MetricSpace --> CR :=
241 Build_UniformlyContinuousFunction cos_uc_prf.
242
243 Definition cos_slow : CR --> CR := Cbind QPrelengthSpace cos_uc.
244
245 Lemma cos_slow_correct : forall x,
246 (IRasCR (Cos x) == cos_slow (IRasCR x))%CR.
247 Proof.
248 intros x.
249 apply: (ContinuousCorrect (I:proper realline)); [apply Continuous_Cos | | constructor].
250 intros q [] _.
251 transitivity (rational_cos q);[|apply rational_cos_correct].
252 unfold cos_slow.
253 pose proof (Cbind_correct QPrelengthSpace cos_uc).
254 apply ucEq_equiv in H.
255 rewrite -> (H (' q))%CR.
256 apply BindLaw1.
257 Qed.
258
259 Definition cos (x:CR) := cos_slow (x - (compress (scale (2*Qceiling (approximate (x*(CRinv_pos (6#1) (scale 2 CRpi))) (Qpos2QposInf (1#2)) -(1#2))) CRpi)))%CR.
260
261 Lemma cos_correct : forall x,
262 (IRasCR (Cos x) == cos (IRasCR x))%CR.
263 Proof.
264 intros x.
265 unfold cos.
266 generalize (Qceiling (approximate (IRasCR x * CRinv_pos (6 # 1) (scale 2 CRpi))
267 (Qpos2QposInf (1 # 2)) - (1 # 2)))%CR.
268 intros z.
269 rewrite -> compress_correct.
270 rewrite <- CRpi_correct, <- CRmult_scale, <- IR_inj_Q_as_CR, <- IR_mult_as_CR,
271 <- IR_minus_as_CR, <- cos_slow_correct.
272 apply IRasCR_wd.
273 rewrite -> inj_Q_mult.
274 change (2:Q) with (Two:Q).
275 rewrite -> inj_Q_nring.
276 rstepr (Cos (x[+]([--](inj_Q IR z))[*](Two[*]Pi))).
277 setoid_replace (inj_Q IR z) with (zring z:IR).
278 rewrite <- zring_inv.
279 symmetry; apply Cos_periodic_Z.
280 rewrite <- inj_Q_zring.
281 apply inj_Q_wd.
282 symmetry; apply zring_Q.
283 Qed.
284
285 (* begin hide *)
286 #[global]
287 Hint Rewrite cos_correct : IRtoCR.
288 (* end hide *)