| 1 |
(* |
| 2 |
Copyright © 2006 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 Import CoRN.model.totalorder.QMinMax. |
| 26 |
Require Import CoRN.reals.fast.CRAlternatingSum. |
| 27 |
Require Import CoRN.reals.fast.CRAlternatingSum_alg. |
| 28 |
Require Import CoRN.reals.fast.CRstreams. |
| 29 |
Require Import CoRN.reals.fast.CRexp. |
| 30 |
Require Import CoRN.reals.fast.CRpi. |
| 31 |
Require Export CoRN.reals.fast.CRArith. |
| 32 |
Require Import CoRN.reals.fast.CRIR. |
| 33 |
From Coq Require Import Qpower Qabs. |
| 34 |
Require Import CoRN.model.ordfields.Qordfield. |
| 35 |
From Coq Require Import Qround. |
| 36 |
Require Import CoRN.transc.Pi. |
| 37 |
Require Import CoRN.reals.fast.ModulusDerivative. |
| 38 |
Require Import CoRN.reals.fast.ContinuousCorrect. |
| 39 |
Require Import CoRN.model.metric2.Qmetric. |
| 40 |
Require Import CoRN.transc.PowerSeries. |
| 41 |
Require Import CoRN.transc.SinCos. |
| 42 |
Require Import CoRN.reals.fast.Compress. |
| 43 |
Require Import CoRN.reals.fast.PowerBound. |
| 44 |
Require Import CoRN.tactics.CornTac. |
| 45 |
Require Import MathClasses.interfaces.abstract_algebra. |
| 46 |
Require Import CoRN.util.Qdlog. |
| 47 |
From Coq Require Import Lia. |
| 48 |
|
| 49 |
(* Backwards compatibility for Hint Rewrite locality attributes *) |
| 50 |
Set Warnings "-unsupported-attributes". |
| 51 |
|
| 52 |
Set Implicit Arguments. |
| 53 |
|
| 54 |
Local Open Scope Q_scope. |
| 55 |
Local Open Scope uc_scope. |
| 56 |
|
| 57 |
Opaque inj_Q CR Qmin Qmax. |
| 58 |
|
| 59 |
Lemma Qmult_pos_neg : forall (a b : Q), |
| 60 |
0 <= a -> b <= 0 -> a*b <= 0. |
| 61 |
Proof. |
| 62 |
intros. rewrite Qmult_comm. |
| 63 |
rewrite <- (Qmult_0_l a). |
| 64 |
apply Qmult_le_compat_r; assumption. |
| 65 |
Qed. |
| 66 |
|
| 67 |
Lemma Qmult_opp_1 : forall q : Q, |
| 68 |
eq (-q) (-1 * q). |
| 69 |
Proof. |
| 70 |
reflexivity. |
| 71 |
Qed. |
| 72 |
|
| 73 |
Lemma fact_inc : forall n:nat, (fact n <= fact (S n))%nat. |
| 74 |
Proof. |
| 75 |
intro n. |
| 76 |
rewrite <- (Nat.mul_1_l (fact n)). |
| 77 |
change (fact (S n)) with ((1+n)*fact n)%nat. |
| 78 |
apply Nat.mul_le_mono_nonneg_r. |
| 79 |
apply (Nat.le_trans _ 1). |
| 80 |
auto. exact (lt_O_fact n). |
| 81 |
apply le_n_S, Nat.le_0_l. |
| 82 |
Qed. |
| 83 |
|
| 84 |
Lemma fact_inc_recurse : forall p n:nat, (n <= p)%nat -> (fact n <= fact p)%nat. |
| 85 |
Proof. |
| 86 |
induction p. |
| 87 |
- intros. inversion H. apply Nat.le_refl. |
| 88 |
- intros. apply Nat.le_succ_r in H. destruct H. |
| 89 |
apply (Nat.le_trans (fact n) (fact p)). |
| 90 |
apply IHp, H. apply fact_inc. |
| 91 |
subst n. apply Nat.le_refl. |
| 92 |
Qed. |
| 93 |
|
| 94 |
(** |
| 95 |
** Sine |
| 96 |
Sine is defined in terms of its alternating Taylor's series. |
| 97 |
*) |
| 98 |
Section SinSeries. |
| 99 |
Variable a:Q. |
| 100 |
|
| 101 |
(* (1,a) -> (3, -a^3/3!) -> ... *) |
| 102 |
Definition sinStream (px : positive*Q) : positive*Q |
| 103 |
:= let d := Pos.succ (fst px) in |
| 104 |
(Pos.add 2 (fst px), - snd px * a * a * (1#(d*Pos.succ d))). |
| 105 |
|
| 106 |
Lemma sinStream_fst : forall p, |
| 107 |
fst (iterate _ sinStream p (1%positive, a)) ≡ Pos.succ (2*p). |
| 108 |
Proof. |
| 109 |
apply Pos.peano_ind. |
| 110 |
- reflexivity. |
| 111 |
- intros p H. rewrite iterate_succ. |
| 112 |
destruct (iterate (positive and Q) sinStream p (1%positive, a)). |
| 113 |
simpl in H. subst p0. |
| 114 |
transitivity (Pos.add 2 (p~1)). reflexivity. |
| 115 |
clear q a. rewrite Pos.mul_succ_r. |
| 116 |
rewrite <- Pos.add_1_l, (Pos.add_comm 1). |
| 117 |
rewrite <- Pos.add_assoc. apply f_equal. reflexivity. |
| 118 |
Qed. |
| 119 |
|
| 120 |
(* The closed formula for the sine stream. *) |
| 121 |
Lemma Str_pth_sinStream : forall (p:positive), |
| 122 |
Str_pth _ sinStream p (xH,a) |
| 123 |
== (1#Pos.of_nat (fact (1+2*Pos.to_nat p))) * ((-1)^p*a^(1+2*p))%Q. |
| 124 |
Proof. |
| 125 |
apply Pos.peano_ind. |
| 126 |
- unfold sinStream, Str_pth; simpl. |
| 127 |
rewrite Qmult_comm. apply Qmult_comp. reflexivity. |
| 128 |
rewrite Qmult_assoc, Qmult_assoc. |
| 129 |
reflexivity. |
| 130 |
- intros p pInd. unfold Str_pth. |
| 131 |
rewrite iterate_succ. unfold Str_pth in pInd. |
| 132 |
pose proof (sinStream_fst p) as H0. |
| 133 |
destruct (iterate (positive and Q) sinStream p (1%positive, a)) as [p0 q]. |
| 134 |
simpl in H0. subst p0. unfold snd in pInd. |
| 135 |
unfold sinStream, snd, fst. |
| 136 |
rewrite pInd. clear pInd q. |
| 137 |
(* Get rid of (-1)^p *) |
| 138 |
rewrite <- (Qmult_comm ((-1) ^ Pos.succ p * a ^ (1 + 2 * Pos.succ p))). |
| 139 |
rewrite <- (Pos.add_1_l p). |
| 140 |
rewrite Pos2Z.inj_add, (Qpower_plus (-1)%Q). |
| 141 |
simpl ((-1)^1). |
| 142 |
rewrite Qmult_opp_1. |
| 143 |
do 5 rewrite <- (Qmult_assoc (-1)). |
| 144 |
apply (Qmult_comp (-1)). reflexivity. |
| 145 |
rewrite (Qmult_comm (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat p)))). |
| 146 |
do 5 rewrite <- (Qmult_assoc ((-1)^p)). |
| 147 |
apply Qmult_comp. reflexivity. |
| 148 |
(* Get rid of a *) |
| 149 |
setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)). |
| 150 |
do 4 rewrite <- (Qmult_assoc (a ^ (1 + 2 * p))). |
| 151 |
apply Qmult_comp. reflexivity. |
| 152 |
rewrite <- (Qmult_assoc _ a a). |
| 153 |
rewrite (Qmult_comm (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat p)))). |
| 154 |
rewrite <- (Qmult_assoc (a*a)). |
| 155 |
apply Qmult_comp. reflexivity. |
| 156 |
(* Get rid of fact *) |
| 157 |
unfold Qeq, Qmult, Qnum, Qden. |
| 158 |
rewrite Z.mul_1_l, Z.mul_1_l. |
| 159 |
rewrite <- (Pos2Nat.id (Pos.succ p~1 * Pos.succ (Pos.succ p~1))). |
| 160 |
rewrite <- Nat2Pos.inj_mul. |
| 161 |
2: apply fact_neq_0. |
| 162 |
replace (fact (1 + 2 * Pos.to_nat (1 + p)))%nat |
| 163 |
with (fact (1 + 2 * Pos.to_nat p) * |
| 164 |
Pos.to_nat (Pos.succ p~1 * Pos.succ (Pos.succ p~1)))%nat. |
| 165 |
reflexivity. |
| 166 |
rewrite Nat.mul_comm. |
| 167 |
replace (1 + 2 * Pos.to_nat (1 + p))%nat with (3 + 2 * Pos.to_nat p)%nat. |
| 168 |
change (fact (3 + 2 * Pos.to_nat p))%nat |
| 169 |
with ((3 + 2 * Pos.to_nat p) |
| 170 |
* ((2 + 2 * Pos.to_nat p) * fact (1 + 2 * Pos.to_nat p)))%nat. |
| 171 |
replace (Pos.to_nat (Pos.succ p~1 * Pos.succ (Pos.succ p~1)))%nat |
| 172 |
with ((3 + 2 * Pos.to_nat p) * ((2 + 2 * Pos.to_nat p)))%nat. |
| 173 |
rewrite Nat.mul_assoc. |
| 174 |
reflexivity. |
| 175 |
(* Finish equalities *) |
| 176 |
rewrite Pos2Nat.inj_mul. |
| 177 |
rewrite Nat.mul_comm. apply f_equal2. |
| 178 |
rewrite Pos2Nat.inj_succ. |
| 179 |
apply (f_equal S). |
| 180 |
rewrite Pos2Nat.inj_xI. reflexivity. |
| 181 |
rewrite Pos2Nat.inj_succ. apply (f_equal S). |
| 182 |
rewrite Pos2Nat.inj_succ. apply (f_equal S). |
| 183 |
rewrite Pos2Nat.inj_xI. reflexivity. |
| 184 |
rewrite Pos2Nat.inj_add. simpl. |
| 185 |
rewrite Nat.add_0_r, Nat.add_succ_r. reflexivity. |
| 186 |
intro abs. |
| 187 |
pose proof (Pos2Nat.is_pos (Pos.succ p~1 * Pos.succ (Pos.succ p~1))). |
| 188 |
rewrite abs in H. inversion H. |
| 189 |
rewrite <- (Qpower_plus_positive a 1 1). |
| 190 |
rewrite <- (Qpower_plus_positive a (1+2*p)). |
| 191 |
apply Qpower_positive_comp. reflexivity. |
| 192 |
rewrite <- Pos.add_assoc. |
| 193 |
apply f_equal. rewrite (Pos.add_comm 1 p). |
| 194 |
reflexivity. |
| 195 |
intro abs. discriminate. |
| 196 |
Qed. |
| 197 |
|
| 198 |
(** Sine is first defined on [[-1,1]] by an alternating series. *) |
| 199 |
Lemma sinStream_alt : -1 <= a <= 1 -> Str_alt_decr _ sinStream (1%positive,a). |
| 200 |
Proof. |
| 201 |
intro Ha. split. |
| 202 |
- (* Replace a by Qabs a *) |
| 203 |
rewrite Str_pth_sinStream, Str_pth_sinStream. |
| 204 |
rewrite Qabs_Qmult, Qabs_Qmult, Qabs_Qmult, Qabs_Qmult. |
| 205 |
rewrite Qabs_Qpower, Qabs_Qpower. |
| 206 |
change (Qabs (-1)) with 1. |
| 207 |
rewrite Qpower_1, Qpower_1, Qmult_1_l, Qmult_1_l. |
| 208 |
rewrite (Qabs_Qpower a (1+2*Pos.succ p)), (Qabs_Qpower a (1+2*p)). |
| 209 |
(* Finish inequality *) |
| 210 |
setoid_replace (Qabs a ^ (1 + 2 * Pos.succ p)%positive) |
| 211 |
with (Qabs a * Qabs a * Qabs a ^ (1 + 2 * p)%positive). |
| 212 |
rewrite Qmult_assoc. |
| 213 |
apply Qmult_le_compat_r. |
| 214 |
2: rewrite <- Qabs_Qpower; apply Qabs_nonneg. |
| 215 |
+ rewrite Qmult_comm. |
| 216 |
apply (Qabs_Qle_condition a 1) in Ha. |
| 217 |
apply (Qle_trans _ (1* (1 # Pos.of_nat (fact (1 + 2 * Pos.to_nat (Pos.succ p)))))). |
| 218 |
apply Qmult_le_compat_r. 2: discriminate. |
| 219 |
apply (Qle_trans _ (1*Qabs a)). |
| 220 |
apply Qmult_le_compat_r. exact Ha. |
| 221 |
apply Qabs_nonneg. rewrite Qmult_1_l. exact Ha. |
| 222 |
rewrite Qmult_1_l. unfold Qabs, Z.abs. |
| 223 |
unfold Qle, Qnum, Qden. |
| 224 |
rewrite Z.mul_1_l, Z.mul_1_l. |
| 225 |
apply Pos2Nat.inj_le. |
| 226 |
rewrite Nat2Pos.id, Nat2Pos.id. |
| 227 |
2: apply fact_neq_0. 2: apply fact_neq_0. |
| 228 |
replace (1 + 2 * Pos.to_nat (Pos.succ p))%nat |
| 229 |
with (2 + (1 + 2 * Pos.to_nat p))%nat |
| 230 |
by (rewrite Pos2Nat.inj_succ; ring). |
| 231 |
apply (Nat.le_trans _ _ _ (fact_inc _)). |
| 232 |
apply fact_inc. |
| 233 |
+ replace (1 + 2 * Pos.succ p)%positive with (2 + (1 + 2 * p))%positive. |
| 234 |
generalize (1 + 2 * p)%positive. clear p. intro p. |
| 235 |
unfold Qpower. |
| 236 |
rewrite Qpower_plus_positive. reflexivity. |
| 237 |
rewrite Pos.add_comm, <- Pos.add_assoc. apply f_equal. |
| 238 |
rewrite <- Pos.add_1_l. |
| 239 |
rewrite Pos.mul_add_distr_l, Pos.mul_1_r. |
| 240 |
apply Pos.add_comm. |
| 241 |
- rewrite Str_pth_sinStream, Str_pth_sinStream. |
| 242 |
rewrite Qmult_comm, <- Qmult_assoc. apply Qmult_pos_neg. |
| 243 |
discriminate. rewrite Qmult_comm, <- Qmult_assoc. |
| 244 |
apply Qmult_pos_neg. discriminate. |
| 245 |
rewrite <- Pos.add_1_l. |
| 246 |
change ((-1) ^ (1 + p)%positive) with (Qpower_positive (-1) (1 + p)). |
| 247 |
rewrite Qpower_plus_positive. simpl (Qpower_positive (-1) 1). |
| 248 |
rewrite <- Qmult_assoc, <- Qmult_assoc. |
| 249 |
apply (Qopp_le_compat 0). |
| 250 |
rewrite (Qmult_comm (a ^ (1 + 2 * (1 + p)%positive))). |
| 251 |
rewrite Qmult_assoc, Qmult_assoc. |
| 252 |
rewrite <- Qmult_assoc. |
| 253 |
apply Qmult_le_0_compat. |
| 254 |
simpl. |
| 255 |
destruct (Qpower_positive (-1) p), Qnum; discriminate. |
| 256 |
setoid_replace (a ^ (1 + 2 * (1 + p))) with (a ^ (1 + 2 * p) * (a * a)). |
| 257 |
rewrite Qmult_assoc. |
| 258 |
apply Qmult_le_0_compat. |
| 259 |
destruct (a ^ (1 + 2 * p)), Qnum; discriminate. |
| 260 |
destruct a, Qnum; discriminate. |
| 261 |
change (a*a) with (Qpower_positive a 2). |
| 262 |
rewrite <- (Qpower_plus_positive a (1+2*p)). |
| 263 |
change (a ^ (1 + 2 * (1 + p))) with (Qpower_positive a (1 + 2 * (1 + p))). |
| 264 |
replace (1 + 2 * (1 + p))%positive with (1 + 2 * p + 2)%positive. |
| 265 |
reflexivity. |
| 266 |
rewrite <- Pos.add_assoc. apply f_equal. |
| 267 |
rewrite Pos.mul_add_distr_l, Pos.mul_1_r. |
| 268 |
apply Pos.add_comm. |
| 269 |
Qed. |
| 270 |
|
| 271 |
Lemma sinStream_zl |
| 272 |
: -1 <= a <= 1 |
| 273 |
-> Limit_zero _ sinStream (xH,a) |
| 274 |
(fun e:Qpos => Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ (proj1_sig e)))))). |
| 275 |
Proof. |
| 276 |
intro Ha. |
| 277 |
intros [e epos]. rewrite Str_pth_sinStream, Qabs_Qmult, Qabs_Qmult. |
| 278 |
rewrite Qabs_Qpower. change (Qabs (-1)) with 1. |
| 279 |
rewrite Qpower_1, Qmult_1_l. |
| 280 |
rewrite Qmult_comm. |
| 281 |
apply (Qle_trans |
| 282 |
_ (1 * Qabs (1 # Pos.of_nat (fact (1+2*(Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))))))))). |
| 283 |
apply Qmult_le_compat_r. 2: apply Qabs_nonneg. |
| 284 |
- rewrite (Qabs_Qpower |
| 285 |
a (1 + 2 * Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ ` (e ↾ epos))))))). |
| 286 |
apply Qpower_le_1. split. |
| 287 |
apply Qabs_nonneg. |
| 288 |
apply Qabs_Qle_condition, Ha. |
| 289 |
- clear Ha a. |
| 290 |
rewrite Qmult_1_l. unfold Qabs, Z.abs, proj1_sig. |
| 291 |
rewrite <- (Qinv_involutive e) at 2. |
| 292 |
assert (0 < /e) as H. |
| 293 |
{ apply Qinv_lt_0_compat, epos. } |
| 294 |
apply (@Qinv_le_compat |
| 295 |
(/e) ((Pos.of_nat (fact (1+2*(Pos.to_nat (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))))))) # 1)). |
| 296 |
exact H. |
| 297 |
apply (Qle_trans _ _ _ (Qceiling_fact_le H)). |
| 298 |
generalize (Pos.succ (Z.to_pos (Z.log2_up (Qceiling (/ e))))). |
| 299 |
clear H epos e. intro p. |
| 300 |
unfold Qle, Qnum, Qden. |
| 301 |
rewrite Z.mul_1_r, Z.mul_1_r. |
| 302 |
apply Pos2Nat.inj_le. |
| 303 |
rewrite Nat2Pos.id, Nat2Pos.id. |
| 304 |
2: apply fact_neq_0. 2: apply fact_neq_0. |
| 305 |
apply fact_inc_recurse. |
| 306 |
apply (Nat.le_trans (Pos.to_nat p) (1 + Pos.to_nat p)). |
| 307 |
apply le_S, Nat.le_refl. |
| 308 |
apply le_n_S. |
| 309 |
rewrite <- (Nat.mul_1_l (Pos.to_nat p)) at 1. |
| 310 |
apply Nat.mul_le_mono_nonneg_r. |
| 311 |
apply Nat.le_0_l. apply le_S, Nat.le_refl. |
| 312 |
Qed. |
| 313 |
|
| 314 |
End SinSeries. |
| 315 |
|
| 316 |
Definition rational_sin_small (a:Q) (p: -1 <= a <= 1) : CR := |
| 317 |
(inject_Q_CR a + AltSeries _ (sinStream a) (xH,a) _ |
| 318 |
(sinStream_alt p) (sinStream_zl p))%CR. |
| 319 |
|
| 320 |
Lemma rational_sin_small_correct : forall (a:Q) (Ha : -1 <= a <= 1), |
| 321 |
(@rational_sin_small a Ha == IRasCR (Sin (inj_Q IR a)))%CR. |
| 322 |
Proof. |
| 323 |
intros a Ha. |
| 324 |
unfold rational_sin_small. |
| 325 |
simpl. |
| 326 |
generalize (fun_series_conv_imp_conv (inj_Q IR a) (inj_Q IR a) |
| 327 |
(leEq_reflexive IR (inj_Q IR a)) sin_ps |
| 328 |
(sin_conv (inj_Q IR a) (inj_Q IR a) (leEq_reflexive IR (inj_Q IR a)) |
| 329 |
(compact_single_iprop realline (inj_Q IR a) I)) (inj_Q IR a) |
| 330 |
(compact_single_prop (inj_Q IR a)) |
| 331 |
(fun_series_inc_IR realline sin_ps sin_conv (inj_Q IR a) I)). |
| 332 |
intros H. |
| 333 |
(* Replace AltSeries by IRasCR (series_sum ...) *) |
| 334 |
rewrite <- (IR_inj_Q_as_CR a). |
| 335 |
rewrite |
| 336 |
(AltSeries_correct |
| 337 |
_ _ _ _ (sinStream_alt Ha) (sinStream_zl Ha) |
| 338 |
_ (AltSeries_convergent_0 _ _ _ _ (inj_Q IR a) |
| 339 |
(sinStream_alt Ha) (sinStream_zl Ha))). |
| 340 |
apply IRasCR_wd. |
| 341 |
- (* Prove the 2 series are equal in IR. |
| 342 |
We need to sum twice as many terms in sin_seq, to get rid of |
| 343 |
the zeros at even indexes. *) |
| 344 |
unfold series_sum. |
| 345 |
apply Lim_seq_eq_Lim_subseq with (fun n => 2*n)%nat. |
| 346 |
intros; lia. |
| 347 |
intros n; exists (S n); lia. |
| 348 |
(* Prove that the partial sums until n are equal. *) |
| 349 |
intros n. |
| 350 |
induction n. |
| 351 |
apply eq_reflexive. |
| 352 |
replace (2*(S n))%nat with (S (S (2*n)))%nat by lia. |
| 353 |
set (n':=(2*n)%nat) in *. |
| 354 |
simpl in *. |
| 355 |
rstepr (seq_part_sum (fun n0 : nat => |
| 356 |
(sin_seq n0[/]nring (R:=IR) (fact n0)[//]nring_fac_ap_zero IR n0)[*] |
| 357 |
nexp IR n0 (inj_Q IR a[-][0])) n'[+]( |
| 358 |
(sin_seq n'[/]nring (R:=IR) (fact n')[//]nring_fac_ap_zero IR n')[*] |
| 359 |
nexp IR n' (inj_Q IR a[-][0])[+] (sin_seq (S n')[/]nring (R:=IR) (fact n' + n' * fact n')[//] |
| 360 |
nring_fac_ap_zero IR (S n'))[*] (nexp IR n' (inj_Q IR a[-][0])[*](inj_Q IR a[-][0])))). |
| 361 |
apply bin_op_wd_unfolded. |
| 362 |
assumption. |
| 363 |
rewrite <- cm_lft_unit. |
| 364 |
unfold sin_seq. |
| 365 |
apply bin_op_wd_unfolded. |
| 366 |
+ destruct (even_or_odd_plus n') as [m [Hm|Hm]]; simpl. |
| 367 |
rational. |
| 368 |
elim (Nat.Even_Odd_False n'); |
| 369 |
[ exists n; subst n'; ring | |
| 370 |
now exists m; rewrite Hm, Nat.add_1_r; simpl; rewrite Nat.add_0_r]. |
| 371 |
+ destruct (even_or_odd_plus (S n')) as [m [Hm|Hm]]; simpl. |
| 372 |
elim (Nat.Even_Odd_False (S n')). |
| 373 |
rewrite Hm. |
| 374 |
replace (m + m)%nat with (2*m)%nat by lia; now exists m. |
| 375 |
subst n'; exists n; ring. |
| 376 |
inversion Hm. |
| 377 |
unfold n' in H1. |
| 378 |
replace m with n by lia. |
| 379 |
clear Hm H1. |
| 380 |
(* Unfold sinStream *) |
| 381 |
transitivity (inj_Q IR ((1#Pos.of_nat (fact (1+2*n))) * ((-1)^n*a^(1+2*n))%Q)). |
| 382 |
clear IHn H. destruct n. simpl. |
| 383 |
apply inj_Q_wd. rewrite Qmult_1_l, Qmult_1_l. reflexivity. |
| 384 |
apply inj_Q_wd. rewrite Str_pth_sinStream. |
| 385 |
rewrite Nat2Pos.id. 2: discriminate. |
| 386 |
replace (Z.pos (Pos.of_nat (S n))) with (Z.of_nat (S n)). |
| 387 |
reflexivity. |
| 388 |
simpl. destruct n. reflexivity. |
| 389 |
rewrite <- Pos.succ_of_nat. reflexivity. discriminate. |
| 390 |
(* Get rid of (-1)^n *) |
| 391 |
transitivity (inj_Q IR ((-(1))^n) [*] (inj_Q IR (a ^ (1 + 2 * n)) [*] inj_Q IR (1 # Pos.of_nat (fact (1 + 2 * n))))). |
| 392 |
rewrite <- inj_Q_mult, <- inj_Q_mult. |
| 393 |
apply inj_Q_wd. rewrite Qmult_comm. rewrite Qmult_assoc. reflexivity. |
| 394 |
change (inj_Q IR ((- (1)) ^ n) [*] (inj_Q IR (a ^ (1 + 2 * n)) |
| 395 |
[*] inj_Q IR (1 # Pos.of_nat (fact (1 + 2 * n)))) |
| 396 |
[=] |
| 397 |
(nexp IR n [--][1][/]nring (R:=IR) (fact (S n'))[//]nring_fac_ap_zero IR (S n'))[*] |
| 398 |
(nexp IR (S n') (inj_Q IR a[-][0]))). |
| 399 |
rstepr ((nexp IR n [--][1][*](nexp IR (S n') (inj_Q IR a[-][0])[/]nring (R:=IR) (fact (S n'))[//] |
| 400 |
nring_fac_ap_zero IR (S n')))). |
| 401 |
apply mult_wd. |
| 402 |
stepr ((inj_Q IR (-(1)))[^]n). |
| 403 |
apply inj_Q_power. |
| 404 |
apply nexp_wd. |
| 405 |
stepr ([--](inj_Q IR 1)). |
| 406 |
apply inj_Q_inv. |
| 407 |
apply un_op_wd_unfolded. |
| 408 |
rstepr (nring 1:IR). |
| 409 |
apply (inj_Q_nring IR 1). |
| 410 |
stepr (inj_Q IR ((1/P_of_succ_nat (pred (fact (1+2*n))))*a^(1+2*n)%nat)). |
| 411 |
rewrite <- inj_Q_mult. |
| 412 |
apply inj_Q_wd. |
| 413 |
rewrite Qmult_comm. |
| 414 |
apply Qmult_comp. |
| 415 |
replace (1 + 2 * Z.of_nat n)%Z with (Z.of_nat (1 + 2 * n)). |
| 416 |
reflexivity. rewrite <- (Nat2Z.inj_mul 2), <- (Nat2Z.inj_add 1). |
| 417 |
reflexivity. pose proof (fact_neq_0 (1+2*n)). |
| 418 |
destruct (fact (1+2*n)). exfalso; apply H0; reflexivity. |
| 419 |
simpl. destruct n0. reflexivity. |
| 420 |
rewrite <- Pos2SuccNat.id_succ, Nat2Pos.id. |
| 421 |
reflexivity. discriminate. |
| 422 |
(* Finish equality *) |
| 423 |
rstepr ((nring 1[/]nring (R:=IR) (fact (S n'))[//] |
| 424 |
nring_fac_ap_zero IR (S n'))[*](nexp IR (S n') (inj_Q IR a[-][0]))). |
| 425 |
change (1+2*n)%nat with (S n'). |
| 426 |
stepr ((inj_Q IR (1 / Zpos (P_of_succ_nat (pred (fact (S n')))))[*](inj_Q IR (a^S n')))). |
| 427 |
apply inj_Q_mult. |
| 428 |
apply mult_wd. |
| 429 |
rewrite <- POS_anti_convert. |
| 430 |
assert (X:inj_Q IR (inject_Z (Z_of_nat (S (pred (fact (S n'))))))[#][0]). |
| 431 |
stepr (inj_Q IR [0]). |
| 432 |
assert (@cs_ap Q_as_CSetoid (inject_Z (Z_of_nat (S (pred (fact (S n')))))) 0). |
| 433 |
discriminate. |
| 434 |
destruct (ap_imp_less _ _ _ X). |
| 435 |
apply less_imp_ap. |
| 436 |
apply inj_Q_less. |
| 437 |
assumption. |
| 438 |
apply Greater_imp_ap. |
| 439 |
apply inj_Q_less. |
| 440 |
assumption. |
| 441 |
apply (inj_Q_nring IR 0). |
| 442 |
stepr ((inj_Q IR 1)[/](inj_Q IR (inject_Z (Z_of_nat (S (pred (fact (S n')))))))[//]X). |
| 443 |
apply inj_Q_div. |
| 444 |
apply div_wd. |
| 445 |
apply (inj_Q_nring IR 1). |
| 446 |
stepl (inj_Q IR (nring (fact (S n')))). |
| 447 |
apply inj_Q_nring. |
| 448 |
assert (Y:=lt_O_fact (S n')). |
| 449 |
apply inj_Q_wd. |
| 450 |
stepr ((fact (S n')):Q). |
| 451 |
clear - n'. |
| 452 |
induction (fact (S n')). |
| 453 |
simpl; reflexivity. |
| 454 |
rewrite inj_S. |
| 455 |
unfold Z.succ. |
| 456 |
simpl in *. |
| 457 |
rewrite -> IHn0. |
| 458 |
rewrite -> injz_plus. |
| 459 |
reflexivity. |
| 460 |
destruct (fact (S n')). |
| 461 |
exfalso; auto with *. |
| 462 |
simpl; reflexivity. |
| 463 |
stepr ((inj_Q IR a)[^](S n')). |
| 464 |
apply inj_Q_power. |
| 465 |
change (inj_Q IR a[^]S n'[=](inj_Q IR a[-][0])[^]S n'). |
| 466 |
apply nexp_wd. |
| 467 |
rational. |
| 468 |
- intro p. |
| 469 |
pose proof (Pos2Nat.is_pos p). destruct (Pos.to_nat p) eqn:des. |
| 470 |
exfalso; inversion H0. |
| 471 |
rewrite <- des. rewrite Pos2Nat.id. reflexivity. |
| 472 |
Qed. |
| 473 |
|
| 474 |
(** Sine's range can then be extended to [[-3^n,3^n]] by [n] applications |
| 475 |
of the identity [sin(x) = 3*sin(x/3) - 4*(sin(x/3))^3]. *) |
| 476 |
Section Sin_Poly. |
| 477 |
|
| 478 |
Definition sin_poly_fun (x:Q) :Q := x*(3 - 4*x*x). |
| 479 |
|
| 480 |
Global Instance: Proper ((=) ==> (=)) sin_poly_fun. |
| 481 |
Proof. unfold sin_poly_fun. solve_proper. Qed. |
| 482 |
|
| 483 |
Lemma sin_poly_fun_correct : forall (q:Q), |
| 484 |
inj_Q IR (sin_poly_fun q)[=]Three[*]inj_Q IR q[-]Four[*](inj_Q IR q[^]3). |
| 485 |
Proof. |
| 486 |
intros q. |
| 487 |
unfold sin_poly_fun. |
| 488 |
stepr (inj_Q IR (3*q-4*q^3)). |
| 489 |
apply inj_Q_wd. |
| 490 |
simpl; ring. |
| 491 |
rewrite inj_Q_minus. |
| 492 |
apply cg_minus_wd. |
| 493 |
stepr (inj_Q IR Three[*]inj_Q IR q). |
| 494 |
apply inj_Q_mult. |
| 495 |
apply mult_wdl. |
| 496 |
apply (inj_Q_nring IR 3). |
| 497 |
stepr (inj_Q IR Four[*]inj_Q IR (q^3)). |
| 498 |
apply inj_Q_mult. |
| 499 |
apply mult_wd. |
| 500 |
apply (inj_Q_nring IR 4). |
| 501 |
apply (inj_Q_power IR q 3). |
| 502 |
Qed. |
| 503 |
|
| 504 |
Definition sin_poly_modulus (e:Qpos) := Qpos2QposInf ((1#9)*e). |
| 505 |
|
| 506 |
Lemma DthreeXMinusFourX3 : Derivative (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))) |
| 507 |
(inj_Q_less _ (-1) 1 eq_refl) |
| 508 |
((Three:IR){**}FId{-}(Four:IR){**}FId{^}3) |
| 509 |
((Three:IR){**}[-C-]([1]:IR){-}(Four:IR){**}((nring 3){**}([-C-][1]{*}FId{^}2))). |
| 510 |
Proof. |
| 511 |
apply Derivative_minus. |
| 512 |
apply Derivative_scal. |
| 513 |
apply Derivative_id. |
| 514 |
apply Derivative_scal. |
| 515 |
apply Derivative_nth. |
| 516 |
apply Derivative_id. |
| 517 |
Qed. |
| 518 |
|
| 519 |
Lemma sin_poly_prf : is_UniformlyContinuousFunction (fun x => sin_poly_fun (QboundAbs (1#1) x)) sin_poly_modulus. |
| 520 |
Proof. |
| 521 |
apply (fun a => is_UniformlyContinuousD_Q |
| 522 |
(Some (-(1))%Q) (Some (1:Q)) eq_refl _ _ DthreeXMinusFourX3 sin_poly_fun a (9#1)). |
| 523 |
simpl; intros q _ _. |
| 524 |
apply sin_poly_fun_correct. |
| 525 |
simpl; intros x' _ [Hx0 Hx1]. |
| 526 |
set (x:=(inj_Q IR x')) in *. |
| 527 |
stepr (Nine:IR); [| now (apply eq_symmetric; apply (inj_Q_nring IR 9))]. |
| 528 |
stepl (ABSIR (Three[-]Twelve[*]x[*]x)); [| now (apply AbsIR_wd; rational)]. |
| 529 |
apply AbsSmall_imp_AbsIR. |
| 530 |
split. |
| 531 |
apply shift_zero_leEq_minus'. |
| 532 |
rstepr (Twelve[*]((nring 1)[-]x)[*](x[-][--](nring 1))). |
| 533 |
repeat apply mult_resp_nonneg. |
| 534 |
apply (nring_nonneg IR 12). |
| 535 |
apply shift_zero_leEq_minus. |
| 536 |
stepr (inj_Q IR (nring 1)); [| now apply inj_Q_nring]. |
| 537 |
assumption. |
| 538 |
apply shift_zero_leEq_minus. |
| 539 |
stepl (inj_Q IR (-(1))). |
| 540 |
assumption. |
| 541 |
stepr ([--](inj_Q IR 1)). |
| 542 |
apply inj_Q_inv. |
| 543 |
apply un_op_wd_unfolded. |
| 544 |
apply (inj_Q_nring IR 1). |
| 545 |
rstepr (Nine[-][0]:IR). |
| 546 |
apply minus_resp_leEq_both. |
| 547 |
apply nring_leEq. |
| 548 |
lia. |
| 549 |
rstepr (Twelve[*]x[^]2). |
| 550 |
apply mult_resp_nonneg. |
| 551 |
apply (nring_leEq IR 0 12). |
| 552 |
lia. |
| 553 |
apply sqr_nonneg. |
| 554 |
Qed. |
| 555 |
|
| 556 |
Definition sin_poly_uc : Q_as_MetricSpace --> Q_as_MetricSpace := |
| 557 |
Build_UniformlyContinuousFunction sin_poly_prf. |
| 558 |
|
| 559 |
Definition sin_poly : CR --> CR |
| 560 |
:= uc_compose compress (Cmap QPrelengthSpace sin_poly_uc). |
| 561 |
|
| 562 |
Lemma sin_poly_correct : forall x, |
| 563 |
AbsSmall (inj_Q IR (1)) x |
| 564 |
-> (IRasCR (Three[*]x[-]Four[*]x[^]3)==sin_poly (IRasCR x))%CR. |
| 565 |
Proof. |
| 566 |
intros x Hx. |
| 567 |
assert (Y:Continuous (clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q))) ((Three:IR){**}FId{-}(Four:IR){**}FId{^}3)). |
| 568 |
eapply Derivative_imp_Continuous. |
| 569 |
apply DthreeXMinusFourX3. |
| 570 |
apply: (ContinuousCorrect |
| 571 |
(I:=(clcr (inj_Q IR (-(1))) (inj_Q IR (1:Q)))) |
| 572 |
(inj_Q_less _ (-1) 1 eq_refl) Y); |
| 573 |
[|repeat constructor|]. |
| 574 |
intros q Hq Hq0. |
| 575 |
transitivity (IRasCR (inj_Q IR (sin_poly_fun q)));[|apply IRasCR_wd; apply sin_poly_fun_correct]. |
| 576 |
simpl. |
| 577 |
change (' q)%CR with (Cunit_fun _ q). |
| 578 |
rewrite -> compress_fun_correct. |
| 579 |
rewrite -> Cmap_fun_correct. |
| 580 |
rewrite -> MonadLaw3. |
| 581 |
rewrite -> IR_inj_Q_as_CR. |
| 582 |
rewrite -> CReq_Qeq. |
| 583 |
simpl. |
| 584 |
unfold sin_poly_fun. |
| 585 |
setoid_replace (Qmax (- (1)) (Qmin 1 q)) with q. |
| 586 |
reflexivity. |
| 587 |
setoid_replace (Qmin 1 q) with q. |
| 588 |
rewrite <- Qle_max_r. |
| 589 |
apply leEq_inj_Q with IR. |
| 590 |
destruct Hq0; assumption. |
| 591 |
rewrite <- Qle_min_r. |
| 592 |
apply leEq_inj_Q with IR. |
| 593 |
destruct Hq0; assumption. |
| 594 |
destruct Hx; split;[stepl [--](inj_Q IR (1:Q)); [| now apply eq_symmetric; apply inj_Q_inv] |];assumption. |
| 595 |
Qed. |
| 596 |
|
| 597 |
Lemma Sin_triple_angle : forall x, (Sin(Three[*]x)[=]Three[*]Sin x[-]Four[*]Sin x[^]3). |
| 598 |
Proof. |
| 599 |
intros x. |
| 600 |
assert (H:Three[*]x[=]x[+]x[+]x) by rational. |
| 601 |
csetoid_rewrite H. |
| 602 |
csetoid_rewrite (Sin_plus (x[+]x) x). |
| 603 |
csetoid_rewrite (Sin_plus x x). |
| 604 |
csetoid_rewrite (Cos_plus x x). |
| 605 |
set (sx:=Sin x). |
| 606 |
set (cx:=Cos x). |
| 607 |
rstepl ((cx[^]2)[*](Three[*]sx)[-]sx[^]3). |
| 608 |
unfold cg_minus. |
| 609 |
csetoid_replace (cx[^]2) ([1][-]sx[^]2). |
| 610 |
rational. |
| 611 |
apply cg_inv_unique_2. |
| 612 |
rstepl ((cx[^]2[+]sx[^]2)[-][1]). |
| 613 |
apply x_minus_x. |
| 614 |
apply FFT. |
| 615 |
Qed. |
| 616 |
|
| 617 |
Lemma shrink_by_three : forall n a, |
| 618 |
-(3^(S n))%Z <= a <= (3^(S n))%Z -> -(3^n)%Z <= a/3 <= (3^n)%Z. |
| 619 |
Proof. |
| 620 |
intros n a H0. |
| 621 |
apply AbsSmall_Qabs. apply AbsSmall_Qabs in H0. |
| 622 |
apply Qmult_lt_0_le_reg_r with (Qabs 3). |
| 623 |
reflexivity. rewrite <- Qabs_Qmult. |
| 624 |
unfold Qdiv. rewrite <- Qmult_assoc. |
| 625 |
setoid_replace (/ 3 * 3) with 1 by reflexivity. |
| 626 |
rewrite Qmult_1_r. |
| 627 |
apply (Qle_trans _ _ _ H0). clear H0. |
| 628 |
change (Qabs 3) with (inject_Z 3). |
| 629 |
rewrite <- (inject_Z_mult (3^n) 3). |
| 630 |
rewrite <- Zle_Qle. |
| 631 |
change (S n) with (1+n)%nat. |
| 632 |
rewrite (Nat2Z.inj_add 1 n). |
| 633 |
rewrite ZBinary.Z.pow_add_r, Z.mul_comm. |
| 634 |
apply Z.le_refl. |
| 635 |
discriminate. |
| 636 |
apply (Nat2Z.inj_le 0), Nat.le_0_l. |
| 637 |
Qed. |
| 638 |
|
| 639 |
Fixpoint rational_sin_bounded (n:nat) (a:Q) : -(3^n)%Z <= a <= (3^n)%Z -> CR := |
| 640 |
match n return -(3^n)%Z <= a <= (3^n)%Z -> CR with |
| 641 |
| O => @rational_sin_small a |
| 642 |
| S n' => fun H => sin_poly (rational_sin_bounded n' (shrink_by_three n' H)) |
| 643 |
end. |
| 644 |
|
| 645 |
Lemma rational_sin_bounded_correct_aux a : |
| 646 |
(sin_poly (IRasCR (Sin (inj_Q IR (a / 3)))) == IRasCR (Sin (inj_Q IR a)))%CR. |
| 647 |
Proof. |
| 648 |
rewrite <- sin_poly_correct; [|apply AbsIR_imp_AbsSmall; |
| 649 |
(stepr (nring 1:IR); [| now apply eq_symmetric; apply (inj_Q_nring IR 1)]); rstepr ([1]:IR); |
| 650 |
apply AbsIR_Sin_leEq_One]. |
| 651 |
apply IRasCR_wd. |
| 652 |
stepl (Sin (inj_Q IR (a/3*3))). |
| 653 |
apply Sin_wd. |
| 654 |
apply inj_Q_wd. |
| 655 |
simpl; field; discriminate. |
| 656 |
generalize (a/3). |
| 657 |
intros b; clear -b. |
| 658 |
stepr (Sin (Three[*](inj_Q IR b))). |
| 659 |
apply Sin_wd. |
| 660 |
stepr ((inj_Q IR b)[*](inj_Q IR (3:Q))). |
| 661 |
apply inj_Q_mult. |
| 662 |
csetoid_replace (inj_Q IR (3:Q)) (Three:IR). |
| 663 |
rational. |
| 664 |
apply (inj_Q_nring IR 3). |
| 665 |
apply Sin_triple_angle. |
| 666 |
Qed. |
| 667 |
|
| 668 |
Lemma rational_sin_bounded_correct : |
| 669 |
forall (n:nat) (a:Q) (Ha : -(3^n #1) <= a <= (3^n #1)), |
| 670 |
(@rational_sin_bounded n a Ha == IRasCR (Sin (inj_Q IR a)))%CR. |
| 671 |
Proof. |
| 672 |
induction n. |
| 673 |
apply rational_sin_small_correct. |
| 674 |
intros a Ha. |
| 675 |
unfold rational_sin_bounded; fold rational_sin_bounded. |
| 676 |
rewrite -> IHn. |
| 677 |
apply rational_sin_bounded_correct_aux. |
| 678 |
Qed. |
| 679 |
End Sin_Poly. |
| 680 |
|
| 681 |
Definition sin_bound (q:Q) : nat := Z.abs_nat (1 + Qdlog 3 (Qabs q)). |
| 682 |
|
| 683 |
Lemma sin_bound_correct : forall q, -(3 ^ sin_bound q #1) ≤ q ≤ (3 ^ sin_bound q #1). |
| 684 |
Proof. |
| 685 |
intro q. |
| 686 |
apply AbsSmall_Qabs. |
| 687 |
unfold sin_bound. |
| 688 |
destruct (Qlt_le_dec (Qabs q) 1). |
| 689 |
- apply (Qle_trans _ 1). |
| 690 |
apply Qlt_le_weak, q0. |
| 691 |
rewrite Qdlog2_le1; simpl; try easy. |
| 692 |
apply Qlt_le_weak, q0. |
| 693 |
- assert (2 ≤ 3%Z) as H by discriminate. |
| 694 |
pose proof (Qdlog_spec 3 (Qabs q) H q0) as [_ H0]. clear H. |
| 695 |
unfold additional_operations.pow, stdlib_rationals.Q_pow in H0. |
| 696 |
assert (0 <= 1 + Qdlog 3 (Qabs q))%Z. |
| 697 |
{ apply semirings.nonneg_plus_compat; [easy | now apply Qdlog_bounded_nonneg]. } |
| 698 |
rewrite inj_Zabs_nat, Z.abs_eq. |
| 699 |
apply Qlt_le_weak. |
| 700 |
rewrite <- Zpower_Qpower in H0. apply H0. |
| 701 |
exact H. exact H. |
| 702 |
Qed. |
| 703 |
|
| 704 |
(** Therefore sin works on all real numbers. *) |
| 705 |
Definition rational_sin (a:Q) : CR := |
| 706 |
rational_sin_bounded (sin_bound a) (sin_bound_correct a). |
| 707 |
|
| 708 |
Lemma rational_sin_correct : forall (a:Q), |
| 709 |
(rational_sin a == IRasCR (Sin (inj_Q IR a)))%CR. |
| 710 |
Proof. |
| 711 |
intros; apply rational_sin_bounded_correct. |
| 712 |
Qed. |
| 713 |
|
| 714 |
#[global] |
| 715 |
Instance: Proper ((=) ==> (=)) rational_sin. |
| 716 |
Proof. |
| 717 |
intros ? ? E. |
| 718 |
rewrite ?rational_sin_correct. |
| 719 |
now apply IRasCR_wd, Sin_wd, inj_Q_wd. |
| 720 |
Qed. |
| 721 |
|
| 722 |
Lemma rational_sin_poly (a : Q) : |
| 723 |
sin_poly (rational_sin (a / 3)) = rational_sin a. |
| 724 |
Proof. |
| 725 |
rewrite ?rational_sin_correct. |
| 726 |
apply rational_sin_bounded_correct_aux. |
| 727 |
Qed. |
| 728 |
|
| 729 |
Lemma rational_sin_correct_aux (a : Q) : |
| 730 |
(- IRasCR (Sin (inj_Q IR (- a)%Q)) == IRasCR (Sin (inj_Q IR a)))%CR. |
| 731 |
Proof. |
| 732 |
rewrite <- IR_opp_as_CR. |
| 733 |
apply IRasCR_wd. |
| 734 |
csetoid_rewrite_rev (Sin_inv (inj_Q IR (-a))). |
| 735 |
apply Sin_wd. |
| 736 |
csetoid_rewrite_rev (inj_Q_inv IR (-a)). |
| 737 |
apply inj_Q_wd. |
| 738 |
simpl. |
| 739 |
ring. |
| 740 |
Qed. |
| 741 |
|
| 742 |
Lemma rational_sin_opp (a : Q) : |
| 743 |
(-rational_sin (-a) = rational_sin a)%CR. |
| 744 |
Proof. |
| 745 |
rewrite ?rational_sin_correct. |
| 746 |
now apply rational_sin_correct_aux. |
| 747 |
Qed. |
| 748 |
|
| 749 |
(** Sine is uniformly continuous everywhere. *) |
| 750 |
Definition sin_uc_prf : is_UniformlyContinuousFunction rational_sin Qpos2QposInf. |
| 751 |
Proof. |
| 752 |
apply (is_UniformlyContinuousFunction_wd) with (fun x => rational_sin x) (Qscale_modulus (1#1)). |
| 753 |
reflexivity. |
| 754 |
intros x. |
| 755 |
simpl. |
| 756 |
autorewrite with QposElim. |
| 757 |
change (/1) with 1. |
| 758 |
replace RHS with (proj1_sig x) by simpl; ring. |
| 759 |
apply Qle_refl. |
| 760 |
apply (is_UniformlyContinuousD None None I Sine Cosine (Derivative_Sin I) rational_sin). |
| 761 |
intros q [] _. |
| 762 |
apply rational_sin_correct. |
| 763 |
intros x [] _. |
| 764 |
stepr ([1]:IR). |
| 765 |
apply: AbsIR_Cos_leEq_One. |
| 766 |
rstepl (nring 1:IR). |
| 767 |
apply eq_symmetric. |
| 768 |
apply (inj_Q_nring IR 1). |
| 769 |
Qed. |
| 770 |
|
| 771 |
Definition sin_uc : Q_as_MetricSpace --> CR := |
| 772 |
Build_UniformlyContinuousFunction sin_uc_prf. |
| 773 |
|
| 774 |
Definition sin_slow : CR --> CR := Cbind QPrelengthSpace sin_uc. |
| 775 |
|
| 776 |
Lemma sin_slow_correct : forall x, |
| 777 |
(IRasCR (Sin x) == sin_slow (IRasCR x))%CR. |
| 778 |
Proof. |
| 779 |
intros x. |
| 780 |
apply: (ContinuousCorrect (I:proper realline)); [apply Continuous_Sin | | constructor]. |
| 781 |
intros q [] _. |
| 782 |
transitivity (rational_sin q);[|apply rational_sin_correct]. |
| 783 |
unfold sin_slow. |
| 784 |
rewrite -> (Cbind_fun_correct QPrelengthSpace sin_uc). |
| 785 |
apply: BindLaw1. |
| 786 |
Qed. |
| 787 |
|
| 788 |
Definition sin (x:CR) := sin_slow (x - (compress (scale (2*Qceiling (approximate (x*(CRinv_pos (6#1) (scale 2 CRpi))) (Qpos2QposInf (1#2)) -(1#2))) CRpi)))%CR. |
| 789 |
|
| 790 |
Lemma sin_correct : forall x, |
| 791 |
(IRasCR (Sin x) == sin (IRasCR x))%CR. |
| 792 |
Proof. |
| 793 |
intros x. |
| 794 |
unfold sin. |
| 795 |
generalize (Qceiling (approximate (IRasCR x * CRinv_pos (6 # 1) (scale 2 CRpi)) |
| 796 |
(Qpos2QposInf (1 # 2)) - (1 # 2)))%CR. |
| 797 |
intros z. |
| 798 |
rewrite -> compress_correct. |
| 799 |
rewrite <- CRpi_correct, <- CRmult_scale, <- IR_inj_Q_as_CR, <- IR_mult_as_CR, |
| 800 |
<- IR_minus_as_CR, <- sin_slow_correct. |
| 801 |
apply IRasCR_wd. |
| 802 |
rewrite -> inj_Q_mult. |
| 803 |
change (2:Q) with (@nring Q_as_CRing 2). |
| 804 |
rewrite -> inj_Q_nring. |
| 805 |
rstepr (Sin (x[+]([--](inj_Q IR z))[*](Two[*]Pi))). |
| 806 |
setoid_replace (inj_Q IR z) with (zring z:IR). |
| 807 |
rewrite <- zring_inv. |
| 808 |
symmetry; apply Sin_periodic_Z. |
| 809 |
rewrite <- inj_Q_zring. |
| 810 |
apply inj_Q_wd. |
| 811 |
symmetry; apply zring_Q. |
| 812 |
Qed. |
| 813 |
|
| 814 |
(* begin hide *) |
| 815 |
#[global] |
| 816 |
Hint Rewrite sin_correct : IRtoCR. |
| 817 |
(* end hide *) |