| 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 *) |